QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#292051#6303. InversionQwertyPi#WA 65ms35100kbC++171.8kb2023-12-27 16:42:232023-12-27 16:42:24

Judging History

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

  • [2023-12-27 16:42:24]
  • 评测
  • 测评结果:WA
  • 用时:65ms
  • 内存:35100kb
  • [2023-12-27 16:42:23]
  • 提交

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

vector<int> G[N];
void add_edge(int u, int v){
    G[u].push_back(v);
}

vector<int> tp;
bool vis[N];
void dfs(int v){
    vis[v] = true;
    for(auto u : G[v]){
        if(!vis[u]) dfs(u);
    }
    tp.push_back(v);
}

void solve(){
    cin >> n;
    forn(i, n + 1) forn(j, n + 1) Q[i][j] = -1;
    mt19937 rng(42);
    for(int tr = 0; tr < 10000; tr++){
        int u, v;
        do{
            u = rng() % n + 1, v = rng() % n + 1;
        }while(u == v);
        if(query2(u, v)){
            add_edge(v, u);
        }else{
            add_edge(u, v);
        }
    }

    vector<int> p(n + 1);
    for(int i = 1; i <= n; i++)
        if (!vis[i]) dfs(i);
    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();
    }
}

詳細信息

Test #1:

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

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: 65ms
memory: 35100kb

input:

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

output:

? 65 1544
? 66 1544
? 65 1543
? 66 1543
? 575 1557
? 576 1557
? 575 1556
? 576 1556
? 289 1114
? 290 1114
? 289 1113
? 290 1113
? 1489 1514
? 1490 1514
? 1489 1513
? 1490 1513
? 519 581
? 520 581
? 519 580
? 520 580
? 583 1151
? 584 1151
? 583 1150
? 584 1150
? 806 1408
? 807 1408
? 806 1407
? 807 1...

result:

wrong answer Wa.