QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#336671#2199. Intriguing SelectionMilanWA 23ms3852kbC++231.6kb2024-02-24 19:05:182024-02-24 19:05:20

Judging History

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

  • [2024-02-24 19:05:20]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3852kb
  • [2024-02-24 19:05:18]
  • 提交

answer

#include <bits/stdc++.h>
#define MULTI int _; cin >> _; while(_--)
#define fi first
#define se second
#define pb(a) push_back(a)
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, n, m) for(int i = n; i <= m; i++)
#define repsv(i, n, m) for(int i = n; i >= m; i--)
#define vsz(a) (int)(a.size())
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;

#ifdef LOCAL
#include "debugs.hpp"
#else
#define dbg(...) 0
#endif

int n;
vi a;

bool ask(int x, int y){
    cout << "? " << x << ' ' << y << '\n';
    char in;
    cin >> in;
    return in == '<';
}

int cmp(int l, int r){
    if(l==r) return a[l];
    else{
        int m = (l+r)/2;
        int v1 = cmp(l, m);
        int v2 = cmp(m+1, r);
        if(v1 != -1) swap(v1, v2);
        if(v1 == -1 && v2 == -1)
            return -1;
        if(v1 == -1)
            return v2;
        if(ask(v1, v2))
            return v1;
        else
            return v2;
    }
}

void solve(){
    cin >> n;
    n *= 2;
    a = vi(n);
    rep(i, n) a[i] = i+1;
    random_device rd; 
    mt19937 g(rd()); 
    shuffle(all(a),g);
    rep(i, n/2){
        int noob = cmp(0, n-1);
        rep(j, n)
            if(a[j]==noob)
                a[j] = -1;
    }
    cout << "!\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    MULTI
    solve();
}

详细

Test #1:

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

input:

2
3
<
>
>
>
<
<
>
<
>
>
<
<
3
>
>
<
>
<
>
>
>
>
<
>
>

output:

? 5 2
? 1 5
? 3 6
? 4 6
? 6 5
? 5 2
? 1 5
? 4 3
? 4 5
? 1 2
? 4 3
? 4 2
!
? 2 5
? 3 5
? 1 4
? 6 1
? 1 5
? 2 5
? 3 5
? 6 4
? 4 5
? 3 2
? 6 4
? 4 3
!

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 23ms
memory: 3852kb

input:

1111
3
>
>
<
>
>
>
<
>
<
>
<
<
3
<
<
>
>
>
<
>
>
<
<
<
<
3
>
>
>
>
>
<
>
>
<
<
<
>
3
>
<
<
>
>
>
<
>
<
>
>
>
3
>
>
<
<
<
>
>
<
>
>
<
>
3
>
>
<
>
<
>
>
<
>
>
<
<
3
>
>
>
>
>
<
>
>
<
<
<
>
3
>
<
<
>
<
>
<
>
>
>
>
<
3
>
>
<
>
<
>
>
>
<
>
>
>
3
>
>
<
<
>
<
<
<
<
<
<
>
3
<
>
>
>
<
<
>
>
<
<
>
>
3
<
>
<
<...

output:

? 3 1
? 2 1
? 5 6
? 4 5
? 5 1
? 2 3
? 5 6
? 4 5
? 5 3
? 2 3
? 4 6
? 4 3
!
? 4 3
? 2 4
? 5 1
? 6 1
? 1 2
? 4 3
? 5 1
? 6 1
? 1 4
? 4 3
? 6 5
? 6 4
!
? 1 4
? 6 4
? 2 5
? 3 5
? 5 4
? 6 1
? 2 5
? 3 5
? 5 6
? 6 1
? 3 2
? 3 6
!
? 3 4
? 5 4
? 6 2
? 1 6
? 6 5
? 3 4
? 6 2
? 1 6
? 6 4
? 3 4
? 1 2
? 2 4
!
? 3 ...

result:

wrong answer Case 27: all players in topn are comparable