QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#653380#3873. Towersf_rs_0 0ms3648kbC++142.7kb2024-10-18 19:59:102024-10-18 19:59:16

Judging History

This is the latest submission verdict.

  • [2024-10-18 19:59:16]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 3648kb
  • [2024-10-18 19:59:10]
  • Submitted

answer

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define tpi tuple<int, int, int, int>
#define il inline
#define p_q priority_queue
#define u_m unordered_map
#define bt bitset
#define rg register

using namespace std;

const int N1 = 300005;
const int N2 = 1000006;
const int mod = 998244353;

using i64 = long long;

void chmin(int& x, int c) {
	x = min(x, c);
}
void chmax(int& x, int c) {
	x = max(x, c);
}

#define debug 1
// #define multi_test_ 1
#define endl '\n'

int _test_ = 1;

namespace zqh {
	int n;
	pii a[1000005];
	vector<int> p;

	void dfs(int u) {
		if (u == n + 1) {
			u_m<int, int> xx, yy;
			for (int x : p) {
				xx[a[x].first]++;
				if (xx[a[x].first] > 2) return;
				yy[a[x].second]++;
				if (yy[a[x].second] > 2) return;
			}
			for (int i = 1; i <= n; i++) {
				bool flag = false;
				for (int x : p) {
					for (int y : p) {
						if (x == y || a[x].first != a[x].first) continue;
						if (i == x || i == y) {
							flag = true;
							continue;
						}
						if (a[x].first != a[i].first) continue;
						if (a[y].first != a[i].first) continue;
						if (a[x].first <= a[i].first && a[i].first <= a[y].first) {
							flag = true;
							continue;
						}
						if (a[y].first <= a[i].first && a[i].first <= a[x].first) {
							flag = true;
							continue;
						}
						return;
					}
				}
				if (!flag) return;
			}
			for (int i = 1; i <= n; i++) {
				bool flag = false;
				for (int x : p) {
					for (int y : p) {
						if (x == y || a[x].second != a[x].second) continue;
						if (i == x || i == y) {
							flag = true;
							continue;
						}
						if (a[x].second != a[i].second) continue;
						if (a[y].second != a[i].second) continue;
						if (a[x].second <= a[i].second && a[i].second <= a[y].second) {
							flag = true;
							continue;
						}
						if (a[y].second <= a[i].second && a[i].second <= a[x].second) {
							flag = true;
							continue;
						}
						return;
					}
				}
				if (!flag) return;
			}
			string s = "";
			for (int i = 1; i <= n; i++) {
				s.push_back('0');
			}
			for (int x : p) {
				s[x - 1] = '1';
			}
			cout << s;
			exit(0);
		}
		dfs(u + 1);
		p.push_back(u);
		dfs(u + 1);
		p.pop_back();
	}

	void init() {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i].first >> a[i].second;
		}
	}

	void solve() {
		dfs(1);
		cout << "-1";
	}

	void main() {
		init();
		solve();
	}
}  // namespace zqh

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef debug
#endif
#ifdef multi_test_
	cin >> _test_;
#endif
	while (_test_--) {
		zqh::main();
	}
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 3592kb

input:

2
869400 218695
664808 31410

output:

11

result:

ok 

Test #2:

score: 5
Accepted
time: 0ms
memory: 3592kb

input:

2
195447 154323
271823 133730

output:

11

result:

ok 

Test #3:

score: 5
Accepted
time: 0ms
memory: 3644kb

input:

3
751594 545975
951568 859051
621150 686048

output:

111

result:

ok 

Test #4:

score: 5
Accepted
time: 0ms
memory: 3648kb

input:

3
404592 259430
770816 43371
147329 582162

output:

111

result:

ok 

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3588kb

input:

3
401670 296316
401670 809250
401670 595959

output:

-1

result:

wrong answer 

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #26:

score: 0
Time Limit Exceeded

input:

92690
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #38:

score: 0
Time Limit Exceeded

input:

1000000
1 18543
4 40327
7 19084
8 44274
10 42366
12 22173
13 9862
15 44706
19 48070
21 13389
24 39273
26 18680
27 46858
28 46126
32 27753
34 28289
36 12220
38 39235
42 28505
45 47348
46 34220
48 47551
50 49156
54 8856
55 25515
56 21932
58 24482
59 20686
61 41381
66 30112
67 44504
70 24510
71 26418
7...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Time Limit Exceeded

Test #85:

score: 0
Time Limit Exceeded

input:

1000000
1 602300
1 778881
2 397065
3 291452
3 678039
5 235300
6 499367
8 8597
10 327718
10 516489
12 416542
12 440048
13 284169
13 383581
13 642202
13 770858
14 378154
14 710033
15 905531
16 50155
17 142259
19 395613
19 500321
20 358934
21 461772
24 562953
24 995887
25 421244
27 900412
29 301006
31 ...

output:


result: