QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191539 | #7535. Limited Shuffle Restoring | Days_of_Future_Past# | WA | 3ms | 4168kb | C++14 | 3.4kb | 2023-09-30 01:01:08 | 2023-09-30 01:01:08 |
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 (ONLINE) {
scanf("%d", &n);
} else {
n = SZ(groundtruth) - 1;
}
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) {
if (cached_query(A, B))
swap(A, B);
ans[A] = 2;
ans[B] = 1;
break;
}
int C = i - 2;
int r1 = rand() % 3;
if (r1 == 1) swap(A, B);
else if (r1 == 2) swap(A, C);
int r2 = rand() % 2;
if (r2 == 1) swap(B, 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);
}
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 + 1, n);
swap(groundtruth[i], groundtruth[j]);
}
//groundtruth = {0, 2, 3, 1, 5, 4};
//printf("ans");
//for (int i = 1; i <= n; ++i)
//printf(" %d", groundtruth[i]);
//printf("\n");
int tc = 1;
while (tc--) {
main2();
}
if (!ONLINE) printf("total query %d\n", query_cnt);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
5 < > > > < > <
output:
? 5 4 ? 4 3 ? 5 3 ? 5 2 ? 3 2 ? 2 1 ? 3 1 ! 2 3 1 5 4
result:
ok yeah, seems ok, spent 7 queries of 13
Test #2:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 3856kb
input:
3 < > <
output:
? 3 2 ? 2 1 ? 3 1 ! 2 3 1
result:
ok yeah, seems ok, spent 3 queries of 10
Test #5:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
4 < > < > <
output:
? 4 3 ? 3 2 ? 4 2 ? 2 1 ? 4 1 ! 2 3 4 1
result:
ok yeah, seems ok, spent 5 queries of 11
Test #6:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
5 < > < > < > <
output:
? 5 4 ? 4 3 ? 5 3 ? 3 2 ? 5 2 ? 2 1 ? 5 1 ! 2 3 4 5 1
result:
ok yeah, seems ok, spent 7 queries of 13
Test #7:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
6 < > < > < > < > >
output:
? 6 5 ? 5 4 ? 6 4 ? 4 3 ? 6 3 ? 3 2 ? 2 1 ? 1 6 ? 2 6 ! 3 2 4 5 6 1
result:
ok yeah, seems ok, spent 9 queries of 15
Test #8:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 < > < > < > < > < > <
output:
? 7 6 ? 6 5 ? 7 5 ? 5 4 ? 7 4 ? 4 3 ? 3 2 ? 2 7 ? 7 1 ? 1 3 ? 7 3 ! 3 4 2 5 6 7 1
result:
ok yeah, seems ok, spent 11 queries of 16
Test #9:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
8 < > < > < > < > < > > > >
output:
? 8 7 ? 7 6 ? 8 6 ? 6 5 ? 8 5 ? 5 4 ? 4 3 ? 3 8 ? 8 2 ? 2 4 ? 1 4 ? 1 8 ? 4 8 ! 3 4 5 2 6 7 8 1
result:
ok yeah, seems ok, spent 13 queries of 18
Test #10:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
9 < > < > < > < > < > > > < > <
output:
? 9 8 ? 8 7 ? 9 7 ? 7 6 ? 9 6 ? 6 5 ? 5 4 ? 4 9 ? 9 3 ? 3 5 ? 2 5 ? 2 9 ? 9 1 ? 1 5 ? 9 5 ! 3 4 5 6 2 7 8 9 1
result:
ok yeah, seems ok, spent 15 queries of 20
Test #11:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
10 < > < > < > < > < > > > < > < > <
output:
? 10 9 ? 9 8 ? 10 8 ? 8 7 ? 10 7 ? 7 6 ? 6 5 ? 5 10 ? 10 4 ? 4 6 ? 3 6 ? 3 10 ? 10 2 ? 2 6 ? 10 6 ? 6 1 ? 10 1 ! 2 4 5 6 7 3 8 9 10 1
result:
ok yeah, seems ok, spent 17 queries of 21
Test #12:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
11 < > < > < > < > < > > > < > < > < > <
output:
? 11 10 ? 10 9 ? 11 9 ? 9 8 ? 11 8 ? 8 7 ? 7 6 ? 6 11 ? 11 5 ? 5 7 ? 4 7 ? 4 11 ? 11 3 ? 3 7 ? 11 7 ? 7 2 ? 11 1 ? 1 2 ? 11 2 ! 3 2 5 6 7 8 4 9 10 11 1
result:
ok yeah, seems ok, spent 19 queries of 23
Test #13:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
12 < > < > < > < > < > > > < > < > < > < > <
output:
? 12 11 ? 11 10 ? 12 10 ? 10 9 ? 12 9 ? 9 8 ? 8 7 ? 7 12 ? 12 6 ? 6 8 ? 5 8 ? 5 12 ? 12 4 ? 4 8 ? 12 8 ? 8 3 ? 12 2 ? 2 3 ? 12 3 ? 3 1 ? 12 1 ! 2 4 3 6 7 8 9 5 10 11 12 1
result:
ok yeah, seems ok, spent 21 queries of 25
Test #14:
score: 0
Accepted
time: 1ms
memory: 4168kb
input:
13 < > < > < > < > < > > > < > < > < > < > > > <
output:
? 13 12 ? 12 11 ? 13 11 ? 11 10 ? 13 10 ? 10 9 ? 9 8 ? 8 13 ? 13 7 ? 7 9 ? 6 9 ? 6 13 ? 13 5 ? 5 9 ? 13 9 ? 9 4 ? 13 3 ? 3 4 ? 13 4 ? 4 2 ? 2 13 ? 2 1 ? 13 1 ! 2 3 5 4 7 8 9 10 6 11 12 13 1
result:
ok yeah, seems ok, spent 23 queries of 26
Test #15:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
14 < > < > < > < > < > > > < > < > < > < > > > < > >
output:
? 14 13 ? 13 12 ? 14 12 ? 12 11 ? 14 11 ? 11 10 ? 10 9 ? 9 14 ? 14 8 ? 8 10 ? 7 10 ? 7 14 ? 14 6 ? 6 10 ? 14 10 ? 10 5 ? 14 4 ? 4 5 ? 14 5 ? 5 3 ? 3 14 ? 3 2 ? 2 1 ? 1 14 ? 2 14 ! 3 2 4 6 5 8 9 10 11 7 12 13 14 1
result:
ok yeah, seems ok, spent 25 queries of 28
Test #16:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
15 < > < > < > < > < > > > < > < > < > < > > > < > < > >
output:
? 15 14 ? 14 13 ? 15 13 ? 13 12 ? 15 12 ? 12 11 ? 11 10 ? 10 15 ? 15 9 ? 9 11 ? 8 11 ? 8 15 ? 15 7 ? 7 11 ? 15 11 ? 11 6 ? 15 5 ? 5 6 ? 15 6 ? 6 4 ? 4 15 ? 4 3 ? 3 2 ? 2 15 ? 3 1 ? 1 15 ? 3 15 ! 3 4 2 5 7 6 9 10 11 12 8 13 14 15 1
result:
ok yeah, seems ok, spent 27 queries of 30
Test #17:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
16 < > < > < > < > < > > > < > < > < > < > > > < > < > > > <
output:
? 16 15 ? 15 14 ? 16 14 ? 14 13 ? 16 13 ? 13 12 ? 12 11 ? 11 16 ? 16 10 ? 10 12 ? 9 12 ? 9 16 ? 16 8 ? 8 12 ? 16 12 ? 12 7 ? 16 6 ? 6 7 ? 16 7 ? 7 5 ? 5 16 ? 5 4 ? 4 3 ? 3 16 ? 4 2 ? 2 16 ? 4 16 ? 4 1 ? 16 1 ! 2 4 5 3 6 8 7 10 11 12 13 9 14 15 16 1
result:
ok yeah, seems ok, spent 29 queries of 31
Test #18:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
17 < > < > < > < > < > > > < > < > < > < > > > < > < > > > > > >
output:
? 17 16 ? 16 15 ? 17 15 ? 15 14 ? 17 14 ? 14 13 ? 13 12 ? 12 17 ? 17 11 ? 11 13 ? 10 13 ? 10 17 ? 17 9 ? 9 13 ? 17 13 ? 13 8 ? 17 7 ? 7 8 ? 17 8 ? 8 6 ? 6 17 ? 6 5 ? 5 4 ? 4 17 ? 5 3 ? 3 17 ? 5 17 ? 5 2 ? 1 2 ? 1 17 ? 2 17 ! 3 2 5 6 4 7 9 8 11 12 13 14 10 15 16 17 1
result:
ok yeah, seems ok, spent 31 queries of 33
Test #19:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
18 < > < > < > < > < > > > < > < > < > < > > > < > < > > > > > > > >
output:
? 18 17 ? 17 16 ? 18 16 ? 16 15 ? 18 15 ? 15 14 ? 14 13 ? 13 18 ? 18 12 ? 12 14 ? 11 14 ? 11 18 ? 18 10 ? 10 14 ? 18 14 ? 14 9 ? 18 8 ? 8 9 ? 18 9 ? 9 7 ? 7 18 ? 7 6 ? 6 5 ? 5 18 ? 6 4 ? 4 18 ? 6 18 ? 6 3 ? 2 3 ? 2 18 ? 1 3 ? 1 18 ? 3 18 ! 3 4 2 6 7 5 8 10 9 12 13 14 15 11 16 17 18 1
result:
ok yeah, seems ok, spent 33 queries of 35
Test #20:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
19 < > < > < > < > < > > > < > < > < > < > > > < > < > > > > > > > < > <
output:
? 19 18 ? 18 17 ? 19 17 ? 17 16 ? 19 16 ? 16 15 ? 15 14 ? 14 19 ? 19 13 ? 13 15 ? 12 15 ? 12 19 ? 19 11 ? 11 15 ? 19 15 ? 15 10 ? 19 9 ? 9 10 ? 19 10 ? 10 8 ? 8 19 ? 8 7 ? 7 6 ? 6 19 ? 7 5 ? 5 19 ? 7 19 ? 7 4 ? 3 4 ? 3 19 ? 2 4 ? 2 19 ? 19 1 ? 1 4 ? 19 4 ! 3 4 5 2 7 8 6 9 11 10 13 14 15 16 12 17 18 ...
result:
ok yeah, seems ok, spent 35 queries of 36
Test #21:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
20 < > < > < > < > < > > > < > < > < > < > > > < > < > > > > > > > < > < > >
output:
? 20 19 ? 19 18 ? 20 18 ? 18 17 ? 20 17 ? 17 16 ? 16 15 ? 15 20 ? 20 14 ? 14 16 ? 13 16 ? 13 20 ? 20 12 ? 12 16 ? 20 16 ? 16 11 ? 20 10 ? 10 11 ? 20 11 ? 11 9 ? 9 20 ? 9 8 ? 8 7 ? 7 20 ? 8 6 ? 6 20 ? 8 20 ? 8 5 ? 4 5 ? 4 20 ? 3 5 ? 3 20 ? 20 2 ? 2 5 ? 5 1 ? 1 20 ? 5 20 ! 3 4 5 6 2 8 9 7 10 12 11 14 ...
result:
ok yeah, seems ok, spent 37 queries of 38
Test #22:
score: -100
Wrong Answer
time: 3ms
memory: 3948kb
input:
111 > > > > > > > > > > < > > > < > > > < > < > > > > > < > < > < > > > > > < > > > > > > > < > > > < > > > < > > > > > > > < > > > > > > > < > > > > > > > > > < > < > < > < > > > < > < > < > > > > > > > > > < > > > < > < > < > < > < > > > > > < > > > > > < > > > > > > > > > > > > > < > < > < > < > ...
output:
? 111 110 ? 111 109 ? 110 109 ? 110 108 ? 109 108 ? 109 107 ? 107 106 ? 107 108 ? 108 105 ? 108 106 ? 104 106 ? 106 105 ? 105 103 ? 105 104 ? 103 104 ? 104 102 ? 103 101 ? 103 102 ? 101 102 ? 102 100 ? 100 101 ? 101 99 ? 99 98 ? 99 100 ? 98 97 ? 98 100 ? 97 100 ? 100 96 ? 95 96 ? 96 97 ? 94 95 ? 95 ...
result:
wrong answer didn't fit into 190 queries