QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#742192 | #9432. Permutation | Sktn0089 | WA | 1ms | 7848kb | C++14 | 2.0kb | 2024-11-13 16:03:34 | 2024-11-13 16:03:39 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll maxn = 2e6 + 10, inf = 1e9;
ll n, a[maxn], b[maxn], id[maxn];
ll query() {
printf("0");
for(ll i = 1; i <= n; i++) printf(" %d", b[i]);
puts(""), fflush(stdout);
ll x; scanf("%d", &x); return x;
}
void solve(ll l, ll r, ll c) {
if(l == r) { a[l] = c; return; }
ll mid = l + r >> 1;
ll e = c == 1? 2 : 1;
for(ll i = 1; i <= n; i++)
if(l <= i && i <= mid) b[i] = c;
else b[i] = e;
if(query()) solve(l, mid, c);
else solve(mid + 1, r, c);
}
void work(ll p, ll q) {
ll l = 1, r = n;
ll lp, rp, lq, rq;
ll e = min(p, q) > 1? 1 : (max(p, q) == 2? 3 : 2);
while(l < r) {
ll mid = l + r >> 1;
for(ll i = 1; i <= n; i++)
if(i > mid && i <= r) b[i] = q;
else b[i] = p;
ll tmp = query();
if(tmp == 0) {
lp = mid + 1, rp = r;
lq = l, rq = mid; break;
}
if(tmp == 2) {
lp = l, rp = mid;
lq = mid + 1, rq = r; break;
}
for(ll i = mid + 1; i <= r; i++) b[i] = e;
if(query()) r = mid;
else l = mid + 1;
}
while(lp < rp && lq < rq) {
ll midp = lp + rp >> 1, midq = lq + rq >> 1;
for(ll i = 1; i <= n; i++)
if(midp < i && i <= rp || lq <= i && i <= midq)
b[i] = q;
else b[i] = p;
ll tmp = query();
if(tmp == 0)
lp = midp + 1, lq = midq + 1;
else if(tmp == 2)
rp = midp, rq = midq;
else {
for(ll i = lq; i <= midq; i++) b[i] = p;
if(query()) rp = midp, lq = midq + 1;
else lp = midp + 1, rq = midq;
}
}
solve(lp, rp, p);
solve(lq, rq, q);
}
int main() {
scanf("%d", &n);
for(ll i = 1; i <= n; i++) id[i] = i;
random_shuffle(id + 1, id + 1 + n);
for(ll i = 1; 2 * i <= n; i++)
work(id[2 * i], id[2 * i - 1]);
if(n & 1) {
for(ll i = 1; i <= n; i++)
if(!a[i]) a[i] = id[n];
} printf("1 ");
for(ll i = 1; i <= n; i++) printf("%d ", a[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7848kb
input:
5 2 1 1 1 1 2 2 2
output:
0 4 4 4 5 5 0 4 4 5 5 4 0 4 4 5 4 4 0 4 1 1 1 1 0 3 3 3 2 2 0 3 3 3 1 1 0 3 3 2 3 3 0 3 1 1 1 1 1 3 1 2 1 5
result:
wrong answer Wrong Anser