QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67777 | #2293. Boredom Buster | He_Ren | WA | 917ms | 11016kb | C++23 | 2.3kb | 2022-12-12 01:15:17 | 2022-12-12 01:15:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
int n;
#ifdef He_Ren
//mt19937_64 gen((unsigned long long)new char ^ time(0));
mt19937_64 gen(0);
int p[MAXN];
void init(void)
{
for(int i=1; i<=n; ++i)
p[i] = (i+1) / 2;
shuffle(p+1, p+n+1, gen);
}
array<int,2> ask(int x,int y)
{
printf("ask %d %d\n",x,y);
if(gen() % 2) swap(p[x], p[y]);
array<int,2> res = {p[x], p[y]};
if(gen() % 2) swap(p[x], p[y]);
return res;
}
void answer(int ans[])
{
printf(" p: ");
for(int i=1; i<=n; ++i)
printf("%d ",p[i]);
printf("\n");
printf("ans: ");
for(int i=1; i<=n; ++i)
printf("%d ",ans[i]);
printf("\n");
}
#else
void init(void)
{
}
array<int,2> ask(int x,int y)
{
printf("? %d %d\n",x,y);
fflush(stdout);
array<int,2> res;
scanf("%d%d",&res[0],&res[1]);
return res;
}
void answer(int ans[])
{
printf("! ");
for(int i=1; i<=n; ++i)
printf("%d ",ans[i]);
printf("\n");
fflush(stdout);
}
#endif
array<int,2> a[MAXN * 2], b[MAXN * 2];
vector<int> pos[MAXN];
int main(void)
{
scanf("%d",&n);
init();
for(int i=1; i<=n/2; ++i)
{
a[i] = {2*i-1, 2*i};
b[i] = ask(a[i][0], a[i][1]);
pos[b[i][0]].emplace_back(i);
pos[b[i][1]].emplace_back(i);
}
auto change = [&] (int i,int x,int y)
{
if(pos[i][0] == x) pos[i][0] = y;
if(pos[i][1] == x) pos[i][1] = y;
};
static int ans[MAXN];
for(int i=1; i<=n/2; ++i)
{
int x = pos[i][0], y = pos[i][1];
if(x == y)
{
ans[a[x][0]] = ans[a[x][1]] = i;
continue;
}
if(b[x][1] == i) swap(b[x][0], b[x][1]);
if(b[y][1] == i) swap(b[y][0], b[y][1]);
while(1)
{
auto cur = ask(a[x][0], a[y][0]);
if((cur[0] == i) == (cur[1] == i))
{
if(cur[0] != i)
{
swap(a[x][0], a[x][1]);
swap(a[y][0], a[y][1]);
}
change(b[x][1], x, y);
swap(a[x][1], a[y][0]);
swap(b[x][1], b[y][0]);
pos[i] = {x, x};
break;
}
cur = ask(a[x][0], a[x][1]);
if((cur[0] == i) == (cur[1] == i))
{
if(cur[0] != i)
{
swap(x, y);
}
change(b[x][1], x, y);
swap(b[x][1], b[y][0]);
pos[i] = {x, x};
break;
}
}
ans[a[x][0]] = ans[a[x][1]] = i;
}
answer(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 917ms
memory: 11016kb
input:
100000 14243 13962 6948 22252 19244 19543 38903 11287 38236 8431 8855 44004 32239 28696 4163 13408 34466 26456 34636 16506 17476 19659 41596 45165 44174 8145 32853 13855 13860 32650 39829 40439 26857 16321 28351 11239 14823 35976 18843 47987 13886 18541 1370 15381 16164 41277 10418 10077 1431 40902 ...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
wrong answer Wrong answer: Too many guesses: 150093 (which is 58093 over).