QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#779013#6303. InversionAnneliese#TL 1ms3776kbC++201.6kb2024-11-24 17:05:392024-11-24 17:05:40

Judging History

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

  • [2024-11-24 17:05:40]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3776kb
  • [2024-11-24 17:05:39]
  • 提交

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++;
    cout << "? " << l << " " << r << "\n";

    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: 3776kb

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

result: