QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191545 | #7535. Limited Shuffle Restoring | Days_of_Future_Past# | WA | 2ms | 3760kb | C++14 | 4.0kb | 2023-09-30 01:05:21 | 2023-09-30 01:05:21 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(c) ((int)(c).size())
#define ONLINE 1
using namespace std;
const int N = 3e4+10;
typedef pair<int, int> pii;
int n;
int a[11];
void dfs(int i) {
if (i == n) {
for (int j = 1; j <= n; ++j)
printf("%d ", a[j]);
puts("");
return;
}
dfs(i + 1);
swap(a[i], a[i+1]);
dfs(i + 1);
swap(a[i], a[i+1]);
if (i + 2 <= n) {
swap(a[i], a[i+2]);
dfs(i + 1);
swap(a[i], a[i+2]);
}
}
void build() {
n = 5;
for (int i = 1; i <= n; ++i)
a[i] = i;
dfs(1);
}
int query_cnt;
vector<int> groundtruth{0, 2, 3, 5, 1, 4};
bool query(int i, int j) {
static char buf[111];
assert(i != j);
printf("? %d %d\n", i, j);
fflush(stdout);
if (ONLINE) {
scanf("%s", buf);
return buf[0] == '<';
} else {
query_cnt++;
int ub = (5 * n) / 3 + 5;
if (query_cnt > ub) {
printf("boom %d\n", ub);
assert(false);
}
return groundtruth[i] < groundtruth[j];
}
}
map<pii, bool> mp;
bool cached_query(int i, int j) {
if (mp.count(pii(i, j))) {
return mp[pii(i, j)];
} else {
bool res = query(i, j);
mp[pii(i, j)] = res;
mp[pii(j, i)] = !res;
return res;
}
}
void answer(const vector<int> &xs) {
printf("!");
for (int i = 1; i <= n; ++i) {
printf(" %d", xs[i]);
if (!ONLINE)
assert(groundtruth[i] == xs[i]);
}
printf("\n");
fflush(stdout);
}
int argmax(const set<int> &cand) {
int mx_i = -1;
for (int x: cand) {
if (mx_i == -1)
mx_i = x;
else if (cached_query(mx_i, x)) {
mx_i = x;
}
}
return mx_i;
}
void main2() {
if (n == 1) {
vector<int> ans(2);
ans[1] = 1;
answer(ans);
return;
}
if (n == 2) {
vector<int> ans(3);
ans[1] = 1;
ans[2] = 2;
if (!query(1, 2))
swap(ans[1], ans[2]);
answer(ans);
return;
}
vector<int> ans(n + 1);
int A = n, B = n - 1;
if (cached_query(A, B))
swap(A, B);
for (int i = n; i > 0; --i) {
//printf("i %d A %d B %d\n", i, A, B);
if (i == 2) {
ans[A] = 2;
ans[B] = 1;
break;
}
int C = i - 2;
if (rand() % 2 == 1)
swap(A, B);
if (rand() % 2 == 1)
swap(B, C);
if (rand() % 2 == 1)
swap(A, C);
if (cached_query(A, B)) { // A < B
if (cached_query(B, C)) { // B < C
ans[C] = i;
} else { // A < B
ans[B] = i;
tie(A, B) = pii(A, C);
}
} else { // A > B
if (cached_query(A, C)) { // A < C
ans[C] = i;
} else {
ans[A] = i;
tie(A, B) = pii(B, C);
}
}
}
answer(ans);
}
void main3() {
if (n == 1) {
vector<int> ans(2);
ans[1] = 1;
answer(ans);
return;
}
if (n == 2) {
vector<int> ans(3);
ans[1] = 1;
ans[2] = 2;
if (!query(1, 2))
swap(ans[1], ans[2]);
answer(ans);
return;
}
vector<int> ans(n + 1);
int A = n, B = n - 1;
if (cached_query(A, B))
swap(A, B);
for (int i = n; i > 0; --i) {
//printf("i %d A %d B %d\n", i, A, B);
if (i == 2) {
ans[A] = 2;
ans[B] = 1;
break;
}
int C = i - 2;
if (cached_query(A, C)) {
ans[C] = i;
} else {
ans[A] = i;
A = C;
if (cached_query(A, B))
swap(A, B);
}
}
answer(ans);
}
int main() {
//build();
//n = 100;
//groundtruth.resize(n + 1);
//for (int i = 1; i <= n; ++i)
//groundtruth[i] = i;
//srand(time(NULL) ^ 0xc2251393);
//for (int i = 1; i <= n; ++i) {
//int j = min(i + rand() % 3, n);
//int j = min(i + 1, n);
//swap(groundtruth[i], groundtruth[j]);
//}
//printf("ans");
//for (int i = 1; i <= n; ++i)
//printf(" %d", groundtruth[i]);
//printf("\n");
int tc = 1;
while (tc--) {
if (ONLINE) {
scanf("%d", &n);
} else {
n = SZ(groundtruth) - 1;
}
if(n <= 20)
main3();
else main2();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
5 < > < > > > >
output:
? 5 4 ? 4 3 ? 3 5 ? 5 2 ? 2 3 ? 2 1 ? 1 3 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 7 queries of 13
Test #2:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 >
output:
? 1 2 ! 2 1
result:
ok yeah, seems ok, spent 1 queries of 8
Test #4:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
3 < > >
output:
? 3 2 ? 2 1 ? 1 3 ! 2 3 1
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 < > > > >
output:
? 4 3 ? 3 2 ? 2 4 ? 2 1 ? 1 4 ! 2 3 4 1
result:
ok yeah, seems ok, spent 5 queries of 11
Test #6:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
5 < > > > > > >
output:
? 5 4 ? 4 3 ? 3 5 ? 3 2 ? 2 5 ? 2 1 ? 1 5 ! 2 3 4 5 1
result:
ok yeah, seems ok, spent 7 queries of 13
Test #7:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
6 < > > > > > > > >
output:
? 6 5 ? 5 4 ? 4 6 ? 4 3 ? 3 6 ? 3 2 ? 2 6 ? 2 1 ? 1 6 ! 2 3 4 5 6 1
result:
ok yeah, seems ok, spent 9 queries of 15
Test #8:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
7 < > > > > > > > > > >
output:
? 7 6 ? 6 5 ? 5 7 ? 5 4 ? 4 7 ? 4 3 ? 3 7 ? 3 2 ? 2 7 ? 2 1 ? 1 7 ! 2 3 4 5 6 7 1
result:
ok yeah, seems ok, spent 11 queries of 16
Test #9:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
8 < > > > > > > > > > > > >
output:
? 8 7 ? 7 6 ? 6 8 ? 6 5 ? 5 8 ? 5 4 ? 4 8 ? 4 3 ? 3 8 ? 3 2 ? 2 8 ? 2 1 ? 1 8 ! 2 3 4 5 6 7 8 1
result:
ok yeah, seems ok, spent 13 queries of 18
Test #10:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
9 < > > > > > > > > > > > > > >
output:
? 9 8 ? 8 7 ? 7 9 ? 7 6 ? 6 9 ? 6 5 ? 5 9 ? 5 4 ? 4 9 ? 4 3 ? 3 9 ? 3 2 ? 2 9 ? 2 1 ? 1 9 ! 2 3 4 5 6 7 8 9 1
result:
ok yeah, seems ok, spent 15 queries of 20
Test #11:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
10 < > > > > > > > > > > > > > > > >
output:
? 10 9 ? 9 8 ? 8 10 ? 8 7 ? 7 10 ? 7 6 ? 6 10 ? 6 5 ? 5 10 ? 5 4 ? 4 10 ? 4 3 ? 3 10 ? 3 2 ? 2 10 ? 2 1 ? 1 10 ! 2 3 4 5 6 7 8 9 10 1
result:
ok yeah, seems ok, spent 17 queries of 21
Test #12:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
11 < > > > > > > > > > > > > > > > > > >
output:
? 11 10 ? 10 9 ? 9 11 ? 9 8 ? 8 11 ? 8 7 ? 7 11 ? 7 6 ? 6 11 ? 6 5 ? 5 11 ? 5 4 ? 4 11 ? 4 3 ? 3 11 ? 3 2 ? 2 11 ? 2 1 ? 1 11 ! 2 3 4 5 6 7 8 9 10 11 1
result:
ok yeah, seems ok, spent 19 queries of 23
Test #13:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
12 < > > > > > > > > > > > > > > > > > > > >
output:
? 12 11 ? 11 10 ? 10 12 ? 10 9 ? 9 12 ? 9 8 ? 8 12 ? 8 7 ? 7 12 ? 7 6 ? 6 12 ? 6 5 ? 5 12 ? 5 4 ? 4 12 ? 4 3 ? 3 12 ? 3 2 ? 2 12 ? 2 1 ? 1 12 ! 2 3 4 5 6 7 8 9 10 11 12 1
result:
ok yeah, seems ok, spent 21 queries of 25
Test #14:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
13 < > > > > > > > > > > > > > > > > > > > > > >
output:
? 13 12 ? 12 11 ? 11 13 ? 11 10 ? 10 13 ? 10 9 ? 9 13 ? 9 8 ? 8 13 ? 8 7 ? 7 13 ? 7 6 ? 6 13 ? 6 5 ? 5 13 ? 5 4 ? 4 13 ? 4 3 ? 3 13 ? 3 2 ? 2 13 ? 2 1 ? 1 13 ! 2 3 4 5 6 7 8 9 10 11 12 13 1
result:
ok yeah, seems ok, spent 23 queries of 26
Test #15:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
14 < > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 14 13 ? 13 12 ? 12 14 ? 12 11 ? 11 14 ? 11 10 ? 10 14 ? 10 9 ? 9 14 ? 9 8 ? 8 14 ? 8 7 ? 7 14 ? 7 6 ? 6 14 ? 6 5 ? 5 14 ? 5 4 ? 4 14 ? 4 3 ? 3 14 ? 3 2 ? 2 14 ? 2 1 ? 1 14 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 1
result:
ok yeah, seems ok, spent 25 queries of 28
Test #16:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
15 < > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 15 14 ? 14 13 ? 13 15 ? 13 12 ? 12 15 ? 12 11 ? 11 15 ? 11 10 ? 10 15 ? 10 9 ? 9 15 ? 9 8 ? 8 15 ? 8 7 ? 7 15 ? 7 6 ? 6 15 ? 6 5 ? 5 15 ? 5 4 ? 4 15 ? 4 3 ? 3 15 ? 3 2 ? 2 15 ? 2 1 ? 1 15 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1
result:
ok yeah, seems ok, spent 27 queries of 30
Test #17:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
16 < > > > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 16 15 ? 15 14 ? 14 16 ? 14 13 ? 13 16 ? 13 12 ? 12 16 ? 12 11 ? 11 16 ? 11 10 ? 10 16 ? 10 9 ? 9 16 ? 9 8 ? 8 16 ? 8 7 ? 7 16 ? 7 6 ? 6 16 ? 6 5 ? 5 16 ? 5 4 ? 4 16 ? 4 3 ? 3 16 ? 3 2 ? 2 16 ? 2 1 ? 1 16 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1
result:
ok yeah, seems ok, spent 29 queries of 31
Test #18:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
17 < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 17 16 ? 16 15 ? 15 17 ? 15 14 ? 14 17 ? 14 13 ? 13 17 ? 13 12 ? 12 17 ? 12 11 ? 11 17 ? 11 10 ? 10 17 ? 10 9 ? 9 17 ? 9 8 ? 8 17 ? 8 7 ? 7 17 ? 7 6 ? 6 17 ? 6 5 ? 5 17 ? 5 4 ? 4 17 ? 4 3 ? 3 17 ? 3 2 ? 2 17 ? 2 1 ? 1 17 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1
result:
ok yeah, seems ok, spent 31 queries of 33
Test #19:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
18 < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 18 17 ? 17 16 ? 16 18 ? 16 15 ? 15 18 ? 15 14 ? 14 18 ? 14 13 ? 13 18 ? 13 12 ? 12 18 ? 12 11 ? 11 18 ? 11 10 ? 10 18 ? 10 9 ? 9 18 ? 9 8 ? 8 18 ? 8 7 ? 7 18 ? 7 6 ? 6 18 ? 6 5 ? 5 18 ? 5 4 ? 4 18 ? 4 3 ? 3 18 ? 3 2 ? 2 18 ? 2 1 ? 1 18 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1
result:
ok yeah, seems ok, spent 33 queries of 35
Test #20:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
19 < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 19 18 ? 18 17 ? 17 19 ? 17 16 ? 16 19 ? 16 15 ? 15 19 ? 15 14 ? 14 19 ? 14 13 ? 13 19 ? 13 12 ? 12 19 ? 12 11 ? 11 19 ? 11 10 ? 10 19 ? 10 9 ? 9 19 ? 9 8 ? 8 19 ? 8 7 ? 7 19 ? 7 6 ? 6 19 ? 6 5 ? 5 19 ? 5 4 ? 4 19 ? 4 3 ? 3 19 ? 3 2 ? 2 19 ? 2 1 ? 1 19 ! 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1...
result:
ok yeah, seems ok, spent 35 queries of 36
Test #21:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
20 < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
output:
? 20 19 ? 19 18 ? 18 20 ? 18 17 ? 17 20 ? 17 16 ? 16 20 ? 16 15 ? 15 20 ? 15 14 ? 14 20 ? 14 13 ? 13 20 ? 13 12 ? 12 20 ? 12 11 ? 11 20 ? 11 10 ? 10 20 ? 10 9 ? 9 20 ? 9 8 ? 8 20 ? 8 7 ? 7 20 ? 7 6 ? 6 20 ? 6 5 ? 5 20 ? 5 4 ? 4 20 ? 4 3 ? 3 20 ? 3 2 ? 2 20 ? 2 1 ? 1 20 ! 2 3 4 5 6 7 8 9 10 11 12 13 ...
result:
ok yeah, seems ok, spent 37 queries of 38
Test #22:
score: -100
Wrong Answer
time: 2ms
memory: 3756kb
input:
111 > < > > < > < > > > < > < > > > < > > > > > > > < > > > > > > > < > > > > > < > > > < > > > < > > > > > < > < > < > < > < > > > < > > > < > > > > > > > > > < > > > > > > > > > > > < > > > < > > > < > > > < > > > > > < > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > < > ...
output:
? 111 110 ? 109 111 ? 109 108 ? 109 110 ? 107 110 ? 110 108 ? 106 107 ? 107 108 ? 108 105 ? 108 106 ? 105 106 ? 106 104 ? 103 104 ? 104 105 ? 105 102 ? 105 103 ? 102 103 ? 103 101 ? 102 100 ? 102 101 ? 101 100 ? 101 99 ? 99 98 ? 99 100 ? 97 98 ? 98 100 ? 100 96 ? 100 97 ? 97 95 ? 97 96 ? 96 95 ? 96 ...
result:
wrong answer didn't fit into 190 queries