QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#135447	#6394. Turn on the Light	UrgantTeam^#	AC ✓	13ms	11228kb	C++23	1.2kb	2023-08-05 15:19:12	2023-08-05 15:19:16

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-08-05 15:19:16]
评测

测评结果：AC
用时：13ms
内存：11228kb

查看

[2023-08-05 15:19:12]
提交

answer

#include<bits/stdc++.h>

using namespace std;

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector < int > res;
    for (int i = 1; i <= n; i++) res.push_back(i);
    int last_ans = 0;
    while (1) {
        int n = res.size();
        int m1 = res[max(n / 4 - 1, 0)];
        int m2 = res[min(n - n / 4, n - 1)];
        cout << "? " << m1 << endl;
        int x1;
        cin >> x1;
        if (x1 == last_ans) {
            cout << "! " << m1 << endl;
            exit(0);
        }
        int x2;
        cout << "? " << m2 << endl;
        cin >> x2;
        if (x2 == x1) {
            cout << "! " << m2 << endl;
            exit(0);
        }
        if (x2 == last_ans) {
            vector < int > new_res;
            for (auto key : res) if (m1 < key && key < m2) new_res.push_back(key);
            res = new_res;
        } else {
            assert(x2 - last_ans == 2);
            vector < int > new_res;
            for (auto key : res) if (key < m1 || key > m2) new_res.push_back(key);
            res = new_res;
        }
        last_ans = x2;
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3464kb

input:

3
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

? 2
? 9
? 3
? 8
? 4
? 7
? 5
! 5

result:

ok Correct position at 5

Test #3:

score: 0

Accepted

time: 1ms

memory: 3524kb

input:

output:

? 2
? 8
? 3
? 7
? 4
? 6
? 5
! 5

result:

ok Correct position at 5

Test #4:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

? 2
? 7
? 3
? 6
? 4
? 5
! 5

result:

ok Correct position at 5

Test #5:

score: 0

Accepted

time: 2ms

memory: 3524kb

input:

output:

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

result:

ok Correct position at 4

Test #6:

score: 0

Accepted

time: 2ms

memory: 3580kb

input:

output:

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

result:

ok Correct position at 4

Test #7:

score: 0

Accepted

time: 1ms

memory: 3516kb

input:

output:

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

result:

ok Correct position at 3

Test #8:

score: 0

Accepted

time: 1ms

memory: 3464kb

input:

output:

? 1
? 4
? 2
? 3
! 3

result:

ok Correct position at 3

Test #9:

score: 0

Accepted

time: 0ms

memory: 3452kb

input:

output:

? 1
? 3
? 2
! 2

result:

ok Correct position at 2

Test #10:

score: 0

Accepted

time: 1ms

memory: 3480kb

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

score: 0

Accepted

time: 1ms

memory: 3568kb

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 11060kb

input:

output:

result:

ok Correct position at 500000

Test #13:

score: 0

Accepted

time: 0ms

memory: 11200kb

input:

output:

result:

ok Correct position at 500001

Test #14:

score: 0

Accepted

time: 3ms

memory: 10984kb

input:

output:

result:

ok Correct position at 499999

Test #15:

score: 0

Accepted

time: 13ms

memory: 11196kb

input:

output:

result:

ok Correct position at 500000

Test #16:

score: 0

Accepted

time: 9ms

memory: 11084kb

input:

output:

result:

ok Correct position at 499998

Test #17:

score: 0

Accepted

time: 10ms

memory: 11156kb

input:

output:

result:

ok Correct position at 499999

Test #18:

score: 0

Accepted

time: 0ms

memory: 11028kb

input:

output:

result:

ok Correct position at 499997

Test #19:

score: 0

Accepted

time: 2ms

memory: 10948kb

input:

output:

result:

ok Correct position at 499998

Test #20:

score: 0

Accepted

time: 2ms

memory: 11204kb

input:

output:

result:

ok Correct position at 499996

Test #21:

score: 0

Accepted

time: 9ms

memory: 10896kb

input:

output:

result:

ok Correct position at 499997

Test #22:

score: 0

Accepted

time: 8ms

memory: 11052kb

input:

output:

result:

ok Correct position at 43

Test #23:

score: 0

Accepted

time: 9ms

memory: 11136kb

input:

output:

result:

ok Correct position at 51

Test #24:

score: 0

Accepted

time: 11ms

memory: 10928kb

input:

output:

result:

ok Correct position at 51

Test #25:

score: 0

Accepted

time: 13ms

memory: 11124kb

input:

output:

result:

ok Correct position at 51

Test #26:

score: 0

Accepted

time: 7ms

memory: 10948kb

input:

output:

result:

ok Correct position at 999781

Test #27:

score: 0

Accepted

time: 9ms

memory: 10992kb

input:

output:

result:

ok Correct position at 999980

Test #28:

score: 0

Accepted

time: 6ms

memory: 11104kb

input:

output:

result:

ok Correct position at 999979

Test #29:

score: 0

Accepted

time: 4ms

memory: 11156kb

input:

output:

result:

ok Correct position at 999978

Test #30:

score: 0

Accepted

time: 6ms

memory: 11104kb

input:

output:

result:

ok Correct position at 499947

Test #31:

score: 0

Accepted

time: 6ms

memory: 11004kb

input:

output:

result:

ok Correct position at 500070

Test #32:

score: 0

Accepted

time: 6ms

memory: 11108kb

input:

output:

result:

ok Correct position at 500076

Test #33:

score: 0

Accepted

time: 7ms

memory: 11020kb

input:

output:

result:

ok Correct position at 499965

Test #34:

score: 0

Accepted

time: 9ms

memory: 10960kb

input:

output:

result:

ok Correct position at 500000

Test #35:

score: 0

Accepted

time: 6ms

memory: 11156kb

input:

output:

result:

ok Correct position at 500000

Test #36:

score: 0

Accepted

time: 13ms

memory: 11228kb

input:

output:

result:

ok Correct position at 499999

Test #37:

score: 0

Accepted

time: 7ms

memory: 11088kb

input:

output:

result:

ok Correct position at 499999

Test #38:

score: 0

Accepted

time: 8ms

memory: 11040kb

input:

output:

result:

ok Correct position at 500001

Test #39:

score: 0

Accepted

time: 12ms

memory: 11012kb

input:

output:

result:

ok Correct position at 500001

Test #40:

score: 0

Accepted

time: 8ms

memory: 11120kb

input:

output:

result:

ok Correct position at 500000

Test #41:

score: 0

Accepted

time: 9ms

memory: 11016kb

input:

output:

result:

ok Correct position at 500000

Test #42:

score: 0

Accepted

time: 5ms

memory: 11056kb

input:

output:

result:

ok Correct position at 1000000

Test #43:

score: 0

Accepted

time: 3ms

memory: 11204kb

input:

output:

result:

ok Correct position at 1