QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#779210 | #6303. Inversion | liuwei# | TL | 1ms | 3612kb | C++14 | 2.0kb | 2024-11-24 17:57:25 | 2024-11-24 17:57:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
#define pre(i, a, b) for(int i = a;i >= b;i--)
#define pb push_back
const int N = 2e3 + 5;
int cnt = 0;
map<pair<int, int>, int>m;
int ask(int l, int r) {
if (l >= r)return 0;
//return 0;
if (m.count({ l,r }))return m[{l, r}];
cnt++;
if(cnt>=40001)while(1);
//return 0;
cout << "? " << l << " " << r << "\n";
int x;
cin >> x;
// cout << "\n";
m[{l, r}] = x;
cout.flush();
return x;
}
int get(int l, int r) {//得到l和r的大小关系
int x = (ask(l, r) - ask(l + 1, r) - ask(l, r - 1) + ask(l + 1, r - 1) + 4) % 2;
return x;
}
int p[N];
int qq[N];
int f[N][N],g[N][N];
void solve(int l, int r) {
if (l == r) {
p[l] = l;
return;
}
int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
int x = mid, y = r;
int len=r-l+1;
vector<int>w;
pre(i, r, l) {
if (x >= l && y > mid)
{
if (get(p[x], p[y])) {
w.pb(p[x]);
x--;
}
else
{
w.pb(p[y]);
y--;
}
}
else if (x >= l) {
w.pb(p[x]);
x--;
}
else {
w.pb(p[y]);
y--;
}
}
rep(i, 0, w.size() - 1) {
p[r - i] = w[i];
}
rep(i,l,r){
qq[p[i]]=i-l+1;
}
int now=0;
rep(i,l,r){
pre(j,i-1,l)
{
if(qq[j]>qq[i])f[j][i]=1;
}
}
rep(i,l,r){
rep(j,i+1,r){
g[i][j]=(f[i][j]+g[i][j-1]+g[i+1][j]-g[i+1][j-1])%2;
m[{i,j}]=g[i][j];
}
}
}
int q[2005];
int main() {
int t = 1;
//cin>> t ;
while (t--) {
int n;
cin >> n;
solve(1, n);
cout << "! ";
rep(i, 1, n) {
q[p[i]] = i;
}
rep(i, 1, n)cout << q[i] << " ";
}
//cout<<cnt<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Time Limit Exceeded
input:
1993 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0...
output:
? 1 2 ? 3 4 ? 2 4 ? 2 3 ? 5 6 ? 7 8 ? 6 8 ? 6 7 ? 5 7 ? 4 8 ? 4 7 ? 3 8 ? 3 7 ? 2 8 ? 2 7 ? 2 6 ? 3 6 ? 2 5 ? 3 5 ? 1 6 ? 1 5 ? 9 10 ? 11 12 ? 9 12 ? 10 12 ? 9 11 ? 10 11 ? 13 14 ? 15 16 ? 13 16 ? 14 16 ? 13 15 ? 14 15 ? 12 13 ? 12 16 ? 12 15 ? 12 14 ? 9 15 ? 10 15 ? 9 14 ? 10 14 ? 11 15 ? 11 14 ? 1...