QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#653380 | #3873. Towers | f_rs_ | 0 | 0ms | 3648kb | C++14 | 2.7kb | 2024-10-18 19:59:10 | 2024-10-18 19:59:16 |
Judging History
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;
}
/*
*/
详细
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 ...