QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#550073#8939. Permutationzhazha21#WA 56ms3660kbC++141.6kb2024-09-07 09:32:032024-09-07 16:12:21

Judging History

This is the latest submission verdict.

  • [2024-09-07 16:12:21]
  • Judged
  • Verdict: WA
  • Time: 56ms
  • Memory: 3660kb
Show
  • [2024-09-07 09:32:03]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const double c = 0.6165551308159;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int l = 1, r = n + 1;
        cout << "? " << l << " " << (r - 1) << endl;
        int p;
        cin >> p;
        while (r - l > 1)
        {
            int k1 = l + c * (r - l) + 0.5, k2 = r - c * (r - l) + 0.5;
            if (p >= k2)
            {
                if (r - k2 == 1)
                    r = k2;
                else
                {
                    cout << "? " << k2 << " " << (r - 1) << endl;
                    int P;
                    cin >> P;
                    if (P == p)
                        l = k2;
                    else
                    {
                        r = k2;
                        cout << "? " << l << " " << (r - 1) << endl;
                        cin >> p;
                    }
                }
            }
            else
            {
                if (k1 - l == 1)
                    l = k1;
                else
                {
                    cout << "? " << l << " " << (k1 - 1) << endl;
                    int P;
                    cin >> P;
                    if (P == p)
                        r = k1;
                    else
                    {
                        l = k1;
                        cout << "? " << l << " " << (r - 1) << endl;
                        cin >> p;
                    }
                }
            }
        }
        cout << "! " << l << endl;
    }
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 56ms
memory: 3660kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 3588kb

input:

10000
3
1
2

output:

? 1 3
? 1 2
? 3 3

result:

wrong answer Integer 3 violates the range [1, 2] (test case 1)
English 繁體中文 简体中文

Server Time: 2025-02-10 23:19:38 | OpenSource Project