QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562002 | #7535. Limited Shuffle Restoring | ucup-team052# | TL | 1ms | 3840kb | C++23 | 3.0kb | 2024-09-13 14:08:11 | 2024-09-13 14:08:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int ord[54][5], used[5], now[5], len;
void dfs(int u) {
if (u == -1) {
memcpy(ord[len], now, sizeof(ord[len]));
++len;
return;
}
int l = max(0, u - 2), r = 4;
for (int i = l; i <= r; i++) {
if (!used[i]) {
used[i] = 1;
now[i] = u;
dfs(u - 1);
used[i] = 0;
}
}
}
map <ull, pair <int, int> > f;
int n;
pair <ull, ull> gao(ull x, int u, int v) {
ull v1 = 0, v2 = 0;
for (int i = 0; i < 54; i++) {
if ((x >> i) & 1) {
if (ord[i][u] < ord[i][v]) v1 |= (1ull << i);
else v2 |= (1ull << i);
}
}
return make_pair(v1, v2);
}
int solve(ull x, int dep) {
if ((x & -x) == x) return dep >= -1;
for (int u = (x == (1ull << 54) - 1 ? 3 : 0); u < 4; u++) {
for (int v = u + 1; v <= 4; v++) {
pair <ull, ull> t = gao(x, u, v);
int cc = max(__builtin_popcountll(t.first), __builtin_popcountll(t.second));
if (__lg(cc) > dep) continue;
int v1 = solve(t.first, dep - 1);
if (!v1) continue;
int v2 = solve(t.second, dep - 1);
if (!v2) continue;
f[x] = make_pair(u, v);
return 1;
}
}
return 0;
}
int ans[30005];
int last;
int query(int u, int v) {
cout << "? " << u << " " << v << endl;
char c;
cin >> c;
return c == '>';
}
int main() {
dfs(4);
solve((1ull << 54) - 1, 5);
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
if (n == 1) {
cout << "! 1" << endl;
return 0;
}
last = query(n - 1, n);
int pos[5] = {0, 0, 0, n - 1, n};
int i;
for (i = n; i >= 5; i -= 3) {
pos[0] = i - 4; pos[1] = i - 3; pos[2] = i - 2;
ull now = (1ull << 54) - 1;
int flag = 0;
while ((now & -now) != now) {
pair <int, int> t = f[now];
int res;
if (!flag) {
flag = 1;
res = last;
} else {
res = query(pos[t.first], pos[t.second]);
}
pair <ull, ull> v = gao(now, t.first, t.second);
if (res) now = v.second;
else now = v.first;
}
int id = 0;
while ((1ull << id) != now) ++id;
// fprintf(stderr, "id = %d\n", id);
// for (int j = 0; j < 5; j++) fprintf(stderr, "ord[%d] = %d, pos[%d] = %d\n", j, ord[id][j], j, pos[j]);
int pos0 = -1, pos1 = -1;
for (int j = 0; j < 5; j++) {
if (ord[id][j] >= 2) {
ans[pos[j]] = i - 4 + ord[id][j];
} else {
if (ord[id][j] == 0) pos0 = pos[j];
else pos1 = pos[j];
}
}
assert(pos0 != -1 && pos1 != -1);
if (pos0 < pos1) {
last = 0;
} else {
last = 1;
swap(pos0, pos1);
}
pos[3] = pos0; pos[4] = pos1;
}
// fprintf(stderr, "i = %d\n", i);
for (; i >= 3; i--) {
pos[2] = i - 2;
int mx = last ? pos[3] : pos[4];
if (query(pos[2], mx)) {
mx = pos[2];
} else {
if (mx == pos[3]) {
pos[3] = pos[2];
} else {
pos[4] = pos[3];
pos[3] = pos[2];
}
last = query(pos[3], pos[4]);
}
ans[mx] = i;
}
if (last) ans[pos[3]] = 2, ans[pos[4]] = 1;
else ans[pos[3]] = 1, ans[pos[4]] = 2;
cout << "!";
for (int i = 1; i <= n; i++) cout << " " << ans[i];
cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
input:
5 > < < > < <
output:
? 4 5 ? 1 5 ? 3 5 ? 1 3 ? 1 2 ? 2 5 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 6 queries of 13
Test #2:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 >
output:
? 1 2 ! 2 1
result:
ok yeah, seems ok, spent 1 queries of 8
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 > < >
output:
? 2 3 ? 1 2 ? 1 3 ! 2 3 1
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
4 > < > < >
output:
? 3 4 ? 2 3 ? 2 4 ? 1 2 ? 1 4 ! 2 3 4 1
result:
ok yeah, seems ok, spent 5 queries of 11
Test #6:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
5 > < > > > >
output:
? 4 5 ? 1 5 ? 3 5 ? 2 5 ? 3 4 ? 2 4 ! 1 4 5 3 2
result:
ok yeah, seems ok, spent 6 queries of 13
Test #7:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
6 > < > > > > < >
output:
? 5 6 ? 2 6 ? 4 6 ? 3 6 ? 4 5 ? 3 5 ? 1 6 ? 1 2 ! 2 1 5 6 4 3
result:
ok yeah, seems ok, spent 8 queries of 15
Test #8:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
7 > < > > > > < > < >
output:
? 6 7 ? 3 7 ? 5 7 ? 4 7 ? 5 6 ? 4 6 ? 2 7 ? 2 3 ? 1 2 ? 1 3 ! 2 3 1 6 7 5 4
result:
ok yeah, seems ok, spent 10 queries of 16
Test #9:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
8 > < > > > > < > > > >
output:
? 7 8 ? 4 8 ? 6 8 ? 5 8 ? 6 7 ? 5 7 ? 1 4 ? 3 4 ? 2 4 ? 3 8 ? 2 8 ! 1 4 5 2 7 8 6 3
result:
ok yeah, seems ok, spent 11 queries of 18
Test #10:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
9 > < > > > > < > > > > < >
output:
? 8 9 ? 5 9 ? 7 9 ? 6 9 ? 7 8 ? 6 8 ? 2 5 ? 4 5 ? 3 5 ? 4 9 ? 3 9 ? 1 5 ? 1 2 ! 2 1 5 6 3 8 9 7 4
result:
ok yeah, seems ok, spent 13 queries of 20
Test #11:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10 > < > > > > < > > > > < > < >
output:
? 9 10 ? 6 10 ? 8 10 ? 7 10 ? 8 9 ? 7 9 ? 3 6 ? 5 6 ? 4 6 ? 5 10 ? 4 10 ? 2 6 ? 2 3 ? 1 2 ? 1 3 ! 2 3 1 6 7 4 9 10 8 5
result:
ok yeah, seems ok, spent 15 queries of 21
Test #12:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
11 > < > > > > < > > > > < > > > >
output:
? 10 11 ? 7 11 ? 9 11 ? 8 11 ? 9 10 ? 8 10 ? 4 7 ? 6 7 ? 5 7 ? 6 11 ? 5 11 ? 1 4 ? 3 4 ? 2 4 ? 3 7 ? 2 7 ! 1 4 5 2 7 8 3 10 11 9 6
result:
ok yeah, seems ok, spent 16 queries of 23
Test #13:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
12 > < > > > > < > > > > < > > > > < >
output:
? 11 12 ? 8 12 ? 10 12 ? 9 12 ? 10 11 ? 9 11 ? 5 8 ? 7 8 ? 6 8 ? 7 12 ? 6 12 ? 2 5 ? 4 5 ? 3 5 ? 4 8 ? 3 8 ? 1 5 ? 1 2 ! 2 1 5 6 3 8 9 4 11 12 10 7
result:
ok yeah, seems ok, spent 18 queries of 25
Test #14:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
13 > < > > > > < > > > > < > > > > < > < >
output:
? 12 13 ? 9 13 ? 11 13 ? 10 13 ? 11 12 ? 10 12 ? 6 9 ? 8 9 ? 7 9 ? 8 13 ? 7 13 ? 3 6 ? 5 6 ? 4 6 ? 5 9 ? 4 9 ? 2 6 ? 2 3 ? 1 2 ? 1 3 ! 2 3 1 6 7 4 9 10 5 12 13 11 8
result:
ok yeah, seems ok, spent 20 queries of 26
Test #15:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
14 > < > > > > < > > > > < > > > > < > > > >
output:
? 13 14 ? 10 14 ? 12 14 ? 11 14 ? 12 13 ? 11 13 ? 7 10 ? 9 10 ? 8 10 ? 9 14 ? 8 14 ? 4 7 ? 6 7 ? 5 7 ? 6 10 ? 5 10 ? 1 4 ? 3 4 ? 2 4 ? 3 7 ? 2 7 ! 1 4 5 2 7 8 3 10 11 6 13 14 12 9
result:
ok yeah, seems ok, spent 21 queries of 28
Test #16:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
15 > < > > > > < > > > > < > > > > < > > > > < >
output:
? 14 15 ? 11 15 ? 13 15 ? 12 15 ? 13 14 ? 12 14 ? 8 11 ? 10 11 ? 9 11 ? 10 15 ? 9 15 ? 5 8 ? 7 8 ? 6 8 ? 7 11 ? 6 11 ? 2 5 ? 4 5 ? 3 5 ? 4 8 ? 3 8 ? 1 5 ? 1 2 ! 2 1 5 6 3 8 9 4 11 12 7 14 15 13 10
result:
ok yeah, seems ok, spent 23 queries of 30
Test #17:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
16 > < > > > > < > > > > < > > > > < > > > > < > < >
output:
? 15 16 ? 12 16 ? 14 16 ? 13 16 ? 14 15 ? 13 15 ? 9 12 ? 11 12 ? 10 12 ? 11 16 ? 10 16 ? 6 9 ? 8 9 ? 7 9 ? 8 12 ? 7 12 ? 3 6 ? 5 6 ? 4 6 ? 5 9 ? 4 9 ? 2 6 ? 2 3 ? 1 2 ? 1 3 ! 2 3 1 6 7 4 9 10 5 12 13 8 15 16 14 11
result:
ok yeah, seems ok, spent 25 queries of 31
Test #18:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
17 > < > > > > < > > > > < > > > > < > > > > < > > > >
output:
? 16 17 ? 13 17 ? 15 17 ? 14 17 ? 15 16 ? 14 16 ? 10 13 ? 12 13 ? 11 13 ? 12 17 ? 11 17 ? 7 10 ? 9 10 ? 8 10 ? 9 13 ? 8 13 ? 4 7 ? 6 7 ? 5 7 ? 6 10 ? 5 10 ? 1 4 ? 3 4 ? 2 4 ? 3 7 ? 2 7 ! 1 4 5 2 7 8 3 10 11 6 13 14 9 16 17 15 12
result:
ok yeah, seems ok, spent 26 queries of 33
Test #19:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
18 > < > > > > < > > > > < > > > > < > > > > < > > > > < >
output:
? 17 18 ? 14 18 ? 16 18 ? 15 18 ? 16 17 ? 15 17 ? 11 14 ? 13 14 ? 12 14 ? 13 18 ? 12 18 ? 8 11 ? 10 11 ? 9 11 ? 10 14 ? 9 14 ? 5 8 ? 7 8 ? 6 8 ? 7 11 ? 6 11 ? 2 5 ? 4 5 ? 3 5 ? 4 8 ? 3 8 ? 1 5 ? 1 2 ! 2 1 5 6 3 8 9 4 11 12 7 14 15 10 17 18 16 13
result:
ok yeah, seems ok, spent 28 queries of 35
Test #20:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
19 > < > > > > < > > > > < > > > > < > > > > < > > > > < > < >
output:
? 18 19 ? 15 19 ? 17 19 ? 16 19 ? 17 18 ? 16 18 ? 12 15 ? 14 15 ? 13 15 ? 14 19 ? 13 19 ? 9 12 ? 11 12 ? 10 12 ? 11 15 ? 10 15 ? 6 9 ? 8 9 ? 7 9 ? 8 12 ? 7 12 ? 3 6 ? 5 6 ? 4 6 ? 5 9 ? 4 9 ? 2 6 ? 2 3 ? 1 2 ? 1 3 ! 2 3 1 6 7 4 9 10 5 12 13 8 15 16 11 18 19 17 14
result:
ok yeah, seems ok, spent 30 queries of 36
Test #21:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
20 > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > >
output:
? 19 20 ? 16 20 ? 18 20 ? 17 20 ? 18 19 ? 17 19 ? 13 16 ? 15 16 ? 14 16 ? 15 20 ? 14 20 ? 10 13 ? 12 13 ? 11 13 ? 12 16 ? 11 16 ? 7 10 ? 9 10 ? 8 10 ? 9 13 ? 8 13 ? 4 7 ? 6 7 ? 5 7 ? 6 10 ? 5 10 ? 1 4 ? 3 4 ? 2 4 ? 3 7 ? 2 7 ! 1 4 5 2 7 8 3 10 11 6 13 14 9 16 17 12 19 20 18 15
result:
ok yeah, seems ok, spent 31 queries of 38
Test #22:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
111 < < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > > > > < > < > > < > > > > < > > > > < > ...
output:
? 110 111 ? 107 110 ? 109 110 ? 108 110 ? 109 111 ? 108 111 ? 104 107 ? 106 107 ? 105 107 ? 106 110 ? 105 110 ? 101 104 ? 103 104 ? 102 104 ? 103 107 ? 102 107 ? 98 101 ? 100 101 ? 99 101 ? 100 104 ? 99 104 ? 95 98 ? 97 98 ? 96 98 ? 97 101 ? 96 101 ? 92 95 ? 94 95 ? 93 95 ? 94 98 ? 93 98 ? 89 92 ? 9...
result:
ok yeah, seems ok, spent 183 queries of 190
Test #23:
score: -100
Time Limit Exceeded
input:
1000 < < < > < > < < < < < < > > > < < > > < > < < > < > < < > < > < < > > < > < < > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >...
output:
? 999 1000 ? 996 999 ? 998 999 ? 996 998 ? 996 997 ? 997 999 ? 993 998 ? 995 998 ? 993 995 ? 994 995 ? 993 994 ? 990 993 ? 992 993 ? 991 993 ? 992 994 ? 991 994 ? 987 990 ? 989 990 ? 988 990 ? 989 993 ? 988 989 ? 984 987 ? 986 987 ? 984 986 ? 984 985 ? 985 987 ? 981 986 ? 983 986 ? 981 983 ? 981 982...