QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180023#6303. Inversionucup-team045#WA 42ms19332kbC++201.7kb2023-09-15 14:41:392023-09-15 14:41:40

Judging History

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

  • [2023-09-15 14:41:40]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:19332kb
  • [2023-09-15 14:41:39]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<random>
using namespace std;
using LL = long long;
int dp[2005][2005];

int main(){

// #ifdef LOCAL
//     freopen("data.in", "r", stdin);
//     freopen("data.out", "w", stdout);
// #endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    memset(dp, -1, sizeof dp);

    auto ask = [&](int l, int r){
        if (l >= r) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        cout << "? " << l + 1 << ' ' << r + 1 << endl;
        int t;
        cin >> t;
        return dp[l][r] = t;
    };
    vector<int> id(n);
    for(int i = 0; i < n; i++) id[i] = i;
    mt19937 rnd(random_device{}());
    shuffle(id.begin(), id.end(), rnd);
    vector<int> c{id[0]};
    for(int i = 1; i < id.size(); i++){

        auto check = [&](int a, int b){
            if (a < b){
                int c1 = ask(a, b);
                int c2 = ask(a + 1, b);
                int c3 = ask(a, b - 1);
                int c4 = ask(a + 1, b - 1);
                return c1 ^ c2 ^ c3 ^ c4;
            }
            swap(a, b);
            int c1 = ask(a, b);
            int c2 = ask(a + 1, b);
            int c3 = ask(a, b - 1);
            int c4 = ask(a + 1, b - 1);
            return c1 ^ c2 ^ c3 ^ c4 ^ 1;
        };

        int l = 0, r = i;
        while(l < r){
            int mid = (l + r) / 2;
            if (check(c[mid], id[i])) r = mid;
            else l = mid + 1; 
        }
        c.insert(c.begin() + r, id[i]);
    }
    vector<int> ans(n);
    for(int i = 0; i < c.size(); i++)
        ans[c[i]] = i;
    cout << "! ";
    for(auto x : ans) cout << x + 1 << ' ';
    cout << endl;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 19332kb

input:

3
0
1
0

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 42ms
memory: 19232kb

input:

1993
0
0
1
1
1
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
0
1
0
0
0
1
1
1
0
1
1
1
0
1
0
1
0
1
1
1
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
1
1
0
1
1
0
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
0
1
0
0
1
0
0
0...

output:

? 813 1635
? 814 1635
? 813 1634
? 814 1634
? 837 1635
? 838 1635
? 837 1634
? 838 1634
? 813 837
? 814 837
? 813 836
? 814 836
? 813 1678
? 814 1678
? 813 1677
? 814 1677
? 837 1678
? 838 1678
? 837 1677
? 838 1677
? 49 813
? 50 813
? 49 812
? 50 812
? 49 1635
? 50 1635
? 49 1634
? 50 1634
? 813 81...

result:

wrong output format Unexpected end of file - int32 expected