QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#187797	#6394. Turn on the Light	rgnerdplayer^#	AC ✓	1ms	3600kb	C++20	1.4kb	2023-09-24 22:45:31	2023-09-24 22:45:31

Judging History

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

[2023-09-24 22:45:31]
评测

测评结果：AC
用时：1ms
内存：3600kb

查看

[2023-09-24 22:45:31]
提交

answer

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

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    auto solve = [&]() {
        int n;
        cin >> n;

        int l = 1, r = n;
        int cl = 0, cr = 0;

        auto query = [&](int i) {
            cout << "? " << i << endl;
            int x;
            cin >> x;
            return x;
        };

        while (l < r) {
            int m = l + r >> 1;

            int x = query(m);

            if (cl != cr) {
                if (x == abs(cl - cr)) {
                    l = r = m;
                } else if (x == abs(cl + 1 - cr)) {
                    l = m + 1;
                    cl++;
                } else {
                    r = m - 1;
                    cr++;
                }
            } else {
                if (x == 0) {
                    l = r = m;
                } else {
                    int y = query(r);
                    if (y == 1) {
                        l = r;
                    } else if (y == 0) {
                        l = m + 1, r--;
                        cl++, cr++;
                    } else {
                        cr += 2;
                        r = m - 1;
                    }
                }
            }
        }

        cout << "! " << l << endl;
    };

    solve();

    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3380kb

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0

Accepted

time: 1ms

memory: 3440kb

input:

output:

? 5
? 10
? 7
? 9
! 8

result:

ok Correct position at 8

Test #3:

score: 0

Accepted

time: 0ms

memory: 3436kb

input:

output:

? 5
? 9
? 2
? 3
! 4

result:

ok Correct position at 4

Test #4:

score: 0

Accepted

time: 0ms

memory: 3424kb

input:

output:

? 4
? 8
? 6
? 7
! 7

result:

ok Correct position at 7

Test #5:

score: 0

Accepted

time: 0ms

memory: 3428kb

input:

output:

? 4
? 7
? 2
! 1

result:

ok Correct position at 1

Test #6:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

output:

? 3
? 6
? 4
? 5
! 5

result:

ok Correct position at 5

Test #7:

score: 0

Accepted

time: 1ms

memory: 3380kb

input:

output:

? 3
? 5
? 1
! 1

result:

ok Correct position at 1

Test #8:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

4
1
1

output:

? 2
? 4
! 4

result:

ok Correct position at 4

Test #9:

score: 0

Accepted

time: 0ms

memory: 3388kb

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #10:

score: 0

Accepted

time: 0ms

memory: 3388kb

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

score: 0

Accepted

time: 0ms

memory: 3428kb

input:

output:

! 1

result:

ok Correct position at 1

Test #12:

score: 0

Accepted

time: 1ms

memory: 3528kb

input:

output:

result:

ok Correct position at 615782

Test #13:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

output:

result:

ok Correct position at 182915

Test #14:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

result:

ok Correct position at 964093

Test #15:

score: 0

Accepted

time: 1ms

memory: 3376kb

input:

output:

result:

ok Correct position at 428281

Test #16:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok Correct position at 716415

Test #17:

score: 0

Accepted

time: 0ms

memory: 3448kb

input:

output:

result:

ok Correct position at 182914

Test #18:

score: 0

Accepted

time: 0ms

memory: 3388kb

input:

output:

result:

ok Correct position at 857037

Test #19:

score: 0

Accepted

time: 1ms

memory: 3384kb

input:

output:

result:

ok Correct position at 428279

Test #20:

score: 0

Accepted

time: 1ms

memory: 3436kb

input:

output:

result:

ok Correct position at 615777

Test #21:

score: 0

Accepted

time: 1ms

memory: 3388kb

input:

output:

result:

ok Correct position at 232967

Test #22:

score: 0

Accepted

time: 1ms

memory: 3524kb

input:

output:

result:

ok Correct position at 43

Test #23:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

output:

result:

ok Correct position at 51

Test #24:

score: 0

Accepted

time: 1ms

memory: 3380kb

input:

output:

result:

ok Correct position at 51

Test #25:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

output:

result:

ok Correct position at 51

Test #26:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

result:

ok Correct position at 999781

Test #27:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

output:

result:

ok Correct position at 999980

Test #28:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

result:

ok Correct position at 999979

Test #29:

score: 0

Accepted

time: 1ms

memory: 3524kb

input:

output:

result:

ok Correct position at 999978

Test #30:

score: 0

Accepted

time: 1ms

memory: 3540kb

input:

output:

result:

ok Correct position at 499947

Test #31:

score: 0

Accepted

time: 1ms

memory: 3412kb

input:

output:

result:

ok Correct position at 500070

Test #32:

score: 0

Accepted

time: 1ms

memory: 3524kb

input:

output:

result:

ok Correct position at 500076

Test #33:

score: 0

Accepted

time: 0ms

memory: 3376kb

input:

output:

result:

ok Correct position at 499965

Test #34:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

output:

result:

ok Correct position at 716668

Test #35:

score: 0

Accepted

time: 1ms

memory: 3424kb

input:

output:

result:

ok Correct position at 433331

Test #36:

score: 0

Accepted

time: 1ms

memory: 3436kb

input:

output:

result:

ok Correct position at 991622

Test #37:

score: 0

Accepted

time: 1ms

memory: 3328kb

input:

output:

result:

ok Correct position at 433330

Test #38:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

output:

result:

ok Correct position at 14602

Test #39:

score: 0

Accepted

time: 1ms

memory: 3384kb

input:

output:

result:

ok Correct position at 14602

Test #40:

score: 0

Accepted

time: 0ms

memory: 3428kb

input:

output:

result:

ok Correct position at 264570

Test #41:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

result:

ok Correct position at 264570

Test #42:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

1000000
1
1

output:

? 500000
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

output:

result:

ok Correct position at 1