QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292055#6303. InversionQwertyPi#WA 55ms34892kbC++171.4kb2023-12-27 16:45:272023-12-27 16:45:27

Judging History

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

  • [2023-12-27 16:45:27]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:34892kb
  • [2023-12-27 16:45:27]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) (a).size()
#define forn(i, n) for(int i = 0; i < (n); i++)

using namespace std;

const int N = 2e3 + 11;
int Q[N][N], query_cnt = 0;
int _query(int l, int r){
    cout << "? " << l << ' ' << r << endl;
    bool res; cin >> res;
    return Q[l][r] = res;
}

int query(int l, int r){
    if(l == r) return 0;
    return Q[l][r] != -1 ? Q[l][r] : _query(l, r);
}

bool query2(int l, int r){ // a[l] > a[r]?
    assert(l != r);
    if(l > r) return !query2(r, l);
    if(l + 1 == r) return query(l, r);
    return query(l, r) ^ query(l + 1, r) ^ query(l, r - 1) ^ query(l + 1, r - 1);
}

int n; 
void answer(vector<int> a){
    assert(sz(a) == n + 1);
    cout << "! ";
    for(int i = 1; i <= n - 1; i++) cout << a[i] << ' ';
    cout << a[n] << endl;
}

void solve(){
    cin >> n;
    forn(i, n + 1) forn(j, n + 1) Q[i][j] = -1;
    mt19937 rng(42);
    
    vector<int> tp(n);
    for(int i = 0; i < n; i++){
        tp[i] = i + 1;
    }

    sort(all(tp), [](int u, int v){
        return query2(u, v);
    });

    vector<int> p(n + 1);
    for(int i = 0; i < n; i++){
        p[tp[i]] = n - i;
    }
    answer(p);
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 55ms
memory: 34892kb

input:

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

output:

? 2 997
? 3 997
? 2 996
? 3 996
? 997 1993
? 998 1993
? 997 1992
? 998 1992
? 2 1993
? 3 1993
? 2 1992
? 3 1992
? 1 2
? 2 3
? 2 4
? 3 4
? 2 5
? 3 5
? 2 1991
? 3 1991
? 2 1990
? 3 1990
? 2 1989
? 3 1989
? 2 1988
? 3 1988
? 2 1987
? 3 1987
? 2 6
? 3 6
? 2 1986
? 3 1986
? 2 7
? 3 7
? 2 1985
? 3 1985
? ...

result:

wrong output format Unexpected end of file - int32 expected