QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#779026#6303. Inversionliuwei#TL 1ms3488kbC++141.7kb2024-11-24 17:08:072024-11-24 17:08:07

Judging History

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

  • [2024-11-24 17:08:07]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3488kb
  • [2024-11-24 17:08:07]
  • 提交

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++;
    if(cnt>=39000)return 0;
    cout << "? " << l << " " << r << "\n";
	cout.flush();
    int x;
    cin >> x;
   // cout << "\n";
    m[{l, r}] = x;
  
    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(1, 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];
    }

}

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] << " ";
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

output:

? 1 2
? 2 3
? 3 4
? 2 4
? 4 5
? 3 5
? 2 5
? 1 5
? 1 4
? 4 6
? 5 6
? 3 6
? 2 6
? 1 6
? 4 7
? 5 7
? 3 7
? 2 7
? 1 7
? 6 7
? 4 8
? 5 8
? 3 8
? 2 8
? 1 3
? 1 8
? 4 9
? 5 9
? 3 9
? 8 9
? 2 9
? 1 9
? 4 10
? 5 10
? 3 10
? 8 10
? 9 10
? 2 10
? 1 10
? 6 10
? 7 10
? 6 9
? 7 9
? 4 11
? 5 11
? 3 11
? 8 11
? 9 1...

result: