QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613419#8939. PermutationnekoyellowWA 6ms3704kbC++201.0kb2024-10-05 14:00:222024-10-05 14:03:30

Judging History

This is the latest submission verdict.

  • [2024-10-05 14:03:30]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 3704kb
Show
  • [2024-10-05 14:00:22]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

int query(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    int res;
    cin >> res;
    return res;
}

void solve() {
    int n;
    cin >> n;
    int l = 1, r = n;
    int k = query(1, n);
    while (r-l > 1) {
        if (k < (l+r)/2) {
            int m = l + max((r-l)/3*2, 1);
            int nk = query(l, m);
            if (k == nk) r = m;
            else {
                l = m+1;
                if (l != r) k = query(l, r);
            }
        } else {
            int m = l + max((r-l)/3, 1);
            int nk = query(m, r);
            if (k == nk) l = m;
            else {
                r = m-1;
                if (l != r) k = query(l, r);
            }
        }
    }
    if (l == r) {
        cout << "! " << l << endl;
    } else {
        cout << "! " << (l == k ? r : l) << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;
    for (; t; t--) solve();

    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5
3
3
3
3
6
6
6
3
4
3
3
3

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 3644kb

input:

10000
10
2
2
2
3
5
10
10
10
10
7
10
5
5
5
4
8
10
4
4
4
4
5
10
10
6
3
2
10
3
3
3
2
10
1
5
9
10
10
1
1
3
6
10
2
4
9
9
10
3
3
3
3
3

output:

? 1 10
? 1 7
? 1 5
? 1 3
? 4 5
! 4
? 1 10
? 4 10
? 6 10
? 7 10
! 6
? 1 10
? 4 10
? 4 8
? 4 6
? 7 8
! 7
? 1 10
? 1 7
? 3 7
? 3 5
? 4 5
! 3
? 1 10
? 4 10
? 1 3
? 2 3
! 1
? 1 10
? 1 7
? 1 5
? 2 5
! 1
? 1 10
? 1 7
? 8 10
? 9 10
! 8
? 1 10
? 1 7
? 1 5
? 6 7
! 7
? 1 10
? 1 7
? 8 10
? 9 10
! 10
? 1 10
? 1 ...

result:

wrong answer Too many queries , n = 10 , now_q 6 (test case 10)
English 繁體中文 简体中文

Server Time: 2025-02-09 05:23:42 | OpenSource Project