QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779090#6303. Inversionliuwei#TL 1ms3584kbC++141.8kb2024-11-24 17:24:362024-11-24 17:24:38

Judging History

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

  • [2024-11-24 17:24:38]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3584kb
  • [2024-11-24 17:24:36]
  • 提交

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;
	
    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];
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;
    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(j,i+1,w.size()-1){
        	if(w[i]<w[j])
        	m[{w[i],w[j]}]=1;
        	else
        	m[{w[j],w[i]}]=0;
		}
    }

}

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<<endl<<cnt<<"!!"<<endl;

    return 0;
}

详细

Test #1:

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

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

output:

? 1 2
? 3 4
? 2 4
? 2 3
? 5 6
? 7 8
? 6 8
? 6 7
? 5 7
? 4 8
? 4 7
? 4 6
? 4 5
? 3 6
? 3 5
? 2 6
? 2 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
? 9 16
? 10 16
? 9 15
? 10 15
? 9 14
? 10 14
? 11 15
? 11 14
? 12 14
...

result: