QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779208#6303. Inversionliuwei#WA 505ms152864kbC++142.0kb2024-11-24 17:56:512024-11-24 17:56:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 17:56:57]
  • 评测
  • 测评结果:WA
  • 用时:505ms
  • 内存:152864kb
  • [2024-11-24 17:56:51]
  • 提交

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++;
	//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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

3
0
1
0

output:

? 1 2
? 2 3
? 1 3
! 2 3 1 

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 505ms
memory: 152864kb

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...

result:

wrong output format Unexpected end of file - int32 expected