QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191542 | #7535. Limited Shuffle Restoring | Days_of_Future_Past# | WA | 1ms | 3760kb | C++14 | 4.0kb | 2023-09-30 01:04:34 | 2023-09-30 01:04:35 |
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 <= 10)
main3();
else main2();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
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: 3660kb
input:
1
output:
! 1
result:
ok yeah, seems ok, spent 0 queries of 6
Test #3:
score: 0
Accepted
time: 1ms
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: 0ms
memory: 3668kb
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: 1ms
memory: 3708kb
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: 3664kb
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: 3664kb
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: 1ms
memory: 3668kb
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: 3636kb
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: 0ms
memory: 3708kb
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: -100
Wrong Answer
time: 1ms
memory: 3736kb
input:
11 < < < > > > > > < > > > > > < > < >
output:
? 11 10 ? 9 10 ? 9 8 ? 8 11 ? 7 11 ? 7 9 ? 6 11 ? 6 9 ? 9 5 ? 5 11 ? 9 11 ? 9 4 ? 3 4 ? 3 11 ? 11 2 ? 2 4 ? 11 4 ? 4 1 ! 1 4 5 3 7 8 9 10 6 11 2
result:
wrong answer this is not the only answer, for example, we could have guessed [2, 4, 5, 3, 7, 8, 9, 10, 6, 11, 1]