QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#636329#9412. Stop the Castlelsflsf2023WA 2ms5984kbC++144.2kb2024-10-12 23:23:192024-10-12 23:23:20

Judging History

This is the latest submission verdict.

  • [2024-10-12 23:23:20]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5984kb
Show
  • [2024-10-12 23:23:19]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

int x[205], y[205];

int r[205], c[205];

int D1[405], D2[405];

int N1[805], N2[805];

set < int > S1[805], S2[805];

int Flag[805][805];

pair < int , int > A[1000005];

int main()
{
	int T;
	scanf("%d", &T);
	while (T --)
	  {
	    int n;
	    scanf("%d", &n);
	    for (int i = 1 ; i <= n ; ++ i)
	      scanf("%d%d", x + i, y + i);
	    int m;
	    scanf("%d", &m);
	    for (int i = 1 ; i <= m ; ++ i)
	      scanf("%d%d", r + i, c + i);
	    map < int , int > M1, M2;
	    for (int i = 1 ; i <= n ; ++ i)
	      D1[i] = x[i], D2[i] = y[i];
	    for (int i = 1 ; i <= m ; ++ i)
	      D1[i + n] = r[i], D2[i + n] = c[i];
	    sort(D1 + 1, D1 + n + m + 1), sort(D2 + 1, D2 + n + m + 1);
	    int N = 0, M = 0;
	    for (int i = 1 ; i <= 4 * n ; ++ i)
	      N1[i] = N2[i] = 0;
	    for (int i = 1 ; i <= n + m ; ++ i)
	      {
	      	if (M1[D1[i]] == 0)
	      	  if (D1[i] == D1[i - 1] + 1)
	      	    M1[D1[i]] = ++ N, N1[N] = D1[i];
	      	  else
	      	    M1[D1[i]] = N += 2, N1[N - 1] = D1[i] - 1, N1[N] = D1[i];
	      	if (M2[D2[i]] == 0)
	      	  if (D2[i] == D2[i - 1] + 1)
	      	    M2[D2[i]] = ++ M, N2[M] = D2[i];
	      	  else
	      	    M2[D2[i]] = M += 2, N2[M - 1] = D2[i] - 1, N2[M] = D2[i];
		  }
		//cout << N << " " << M << endl;
		for (int i = 1 ; i <= n ; ++ i)
		  x[i] = M1[x[i]], y[i] = M2[y[i]];
		for (int i = 1 ; i <= m ; ++ i)
		  r[i] = M1[r[i]], c[i] = M2[c[i]];
		//for (int i = 1 ; i <= n ; ++ i)
		  //printf("%d %d\n", x[i], y[i]);
		//for (int i = 1 ; i <= m ; ++ i)
		  //printf("%d %d\n", r[i], c[i]);
		for (int i = 1 ; i <= N ; ++ i)
		  S1[i].clear();
		for (int i = 1 ; i <= M ; ++ i)
		  S2[i].clear();
		for (int i = 1 ; i <= N ; ++ i)
		  for (int j = 1 ; j <= M ; ++ j)
		    Flag[i][j] = 0;
		for (int i = 1 ; i <= n ; ++ i)
		  Flag[x[i]][y[i]] = 1, S1[x[i]].insert(y[i]), S2[y[i]].insert(x[i]);
		for (int i = 1 ; i <= m ; ++ i)
		  Flag[r[i]][c[i]] = 2, S1[r[i]].insert(c[i]), S2[c[i]].insert(r[i]);
		bool F = false;
		for (int i = 2 ; i <= N ; ++ i)
		  for (int j = 2 ; j <= M ; ++ j)
		    if (Flag[i][j] == 1 && Flag[i - 1][j] == 1 || Flag[i][j] == 1 && Flag[i][j - 1] == 1)
		      F = true;
		if (F)
		  {
		  	puts("-1");
		  	continue;
		  }
		int Ans = 0;
		for (int i = 1 ; i <= N ; ++ i)
		  for (int j = 1 ; j <= M ; ++ j)
	        if (Flag[i][j] == 0)
		      {
		      	//if (N1[i] == 0 || N2[j] == 0)
		      	  //continue;
		      	int R = 0;
		      	set < int > :: iterator k = S1[i].upper_bound(j);
		      	if (k == S1[i].end() || k == S1[i].begin())
		      	  continue;
		      	int Y2 = *k, Y1 = *(-- k);
		      	if (Flag[i][Y1] == 1 && Flag[i][Y2] == 1)
		      	  ++ R;
		      	k = S2[j].upper_bound(i);
		      	if (k == S2[j].end() || k == S2[j].begin())
		      	  continue;
		      	int X2 = *k, X1 = *(-- k);
		        if (Flag[X1][j] == 1 && Flag[X2][j] == 1)
		          ++ R;
		        if (R == 2)
		          Flag[i][j] = 2, S1[i].insert(j), S2[j].insert(i), A[++ Ans] = make_pair(N1[i], N2[j]);
			  }
		for (int i = 1 ; i <= N ; ++ i)
		  for (int j = 1 ; j <= M ; ++ j)
		    if (Flag[i][j] == 0)
		      {
		      	//if (N1[i] == 0 || N2[j] == 0)
		      	  //continue;
		      	int R = 0;
		      	set < int > :: iterator k = S1[i].upper_bound(j);
		      	if ( !(k == S1[i].end() || k == S1[i].begin() ) )
		      	  {
					
		      	int Y2 = *k, Y1 = *(-- k);
		      	if (Flag[i][Y1] == 1 && Flag[i][Y2] == 1)
		      	  ++ R;
		        if (R)
		          {
		            Flag[i][j] = 2, S1[i].insert(j), S2[j].insert(i), A[++ Ans] = make_pair(N1[i], N2[j]);
		            continue;
		          }
		      }
		      	k = S2[j].upper_bound(i);
		      	if (k == S2[j].end() || k == S2[j].begin())
		      	  continue;
		      	int X2 = *k, X1 = *(-- k);
		        if (Flag[X1][j] == 1 && Flag[X2][j] == 1)
		          ++ R;
		        if (R)
		          Flag[i][j] = 2, S1[i].insert(j), S2[j].insert(i), A[++ Ans] = make_pair(N1[i], N2[j]);
			  }
		printf("%d\n", Ans);
		for (int i = 1 ; i <= Ans ; ++ i)
		  printf("%d %d\n", A[i].first, A[i].second);
	  }
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5944kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 5984kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
23 12
29 38
40 18
5
13 6
16 10
16 15
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 16
33 11
42 44
44 45
0
5
9 1
22 15
27 41
29 27
44 4
1
32 10
0
0
0
0
6
23 10
35 34
12 12
23 44
24 46
29 23
0
3
20 30
32 17
43 25
0
2
15 7
3 8
3
16 36
17 39
25 7
6
5 5
8 9
2 11
3 10
6 4
7 3

result:

wrong answer There are still 1 pairs of castles which can attack each other (test case 19)
English 繁體中文 简体中文

服务器时间: 2025-02-08 22:19:37 | 开源项目