QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#538045#6394. Turn on the LightwiqqAC ✓1ms3692kbC++171.4kb2024-08-30 21:37:022024-08-30 21:37:02

Judging History

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

  • [2024-08-30 21:37:02]
  • 评测
  • 测评结果：AC
  • 用时：1ms
  • 内存：3692kb
查看
  • [2024-08-30 21:37:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define IOS cin.tie(0), ios::sync_with_stdio(false)
#define endl '\n'
#define int long long
#define pii pair<int, int>
#define mod 998244353
const int N = 1e6 + 6;
int query(int x)
{
    cout << '?' << " " << x << endl;
    cout.flush();
    cin >> x;
    return x;
}
void print(int x)
{
    cout <<'!'<<' '<< x << endl;
    cout.flush();
}
void solve()
{
    int n;
    cin >> n;
    int l = 1, r = n;
    int last = 0;
    while (1)
    {
        int now = query(l);
        if (now == last)
        {
            print(l);
            return;
        }
        l++;
        last = now;
        while (l <= r)
        {
            int mid = l + r + 1 >> 1;
            now = query(mid);
            if(now==last)
            {
                print(mid);
                return;
            }
            if (now < last)
            {
                r = mid - 1;
                last = now;
                break;
            }
            else
            {
                l = mid + 1;
                last = now;
            }
        }
        if(l==r)
        {
            print(l);
            return;
        }
    }
}
signed main()
{

    // IOS;
    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    // cout << ans << endl;
  //  system("pause");
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

3
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

10
1
0
1
0

output:

? 1
? 6
? 2
? 4
! 3

result:

ok Correct position at 3

Test #3:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

9
1
0
1
0

output:

? 1
? 6
? 2
? 4
! 3

result:

ok Correct position at 3

Test #4:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

8
1
0
1
0

output:

? 1
? 5
? 2
? 4
! 3

result:

ok Correct position at 3

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

7
1
0
1
0

output:

? 1
? 5
? 2
? 4
! 3

result:

ok Correct position at 3

Test #6:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

6
1
0
1
1

output:

? 1
? 4
? 2
? 3
! 3

result:

ok Correct position at 3

Test #7:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

5
1
0
1
1

output:

? 1
? 4
? 2
? 3
! 3

result:

ok Correct position at 3

Test #8:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

3
1
0

output:

? 1
? 3
! 2

result:

ok Correct position at 2

Test #10:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
1
2
3
2
3
2
3
2
3
2
3
4
5
4
5
4
5
4

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 11725
? 7820
? 9773
? 7821
? 8797
? 9285
? 8798
? 9042
? 8799
? 8921
? 8800
? 8861
? 8801
? 8831
? 8846
? 8854
? 8847
? 8851
? 8848
? 8850
! 8849

result:

ok Correct position at 8849

Test #13:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
1
2
3
2
3
2
3
2
3
2
3
4
5
4
5
4
5
4

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 11725
? 7820
? 9773
? 7821
? 8797
? 9285
? 8798
? 9042
? 8799
? 8921
? 8800
? 8861
? 8801
? 8831
? 8846
? 8854
? 8847
? 8851
? 8848
? 8850
! 8849

result:

ok Correct position at 8849

Test #14:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

999998
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #15:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

999997
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #16:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

999996
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499999
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #17:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

999995
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499999
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #18:

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

input:

999994
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499998
? 2
? 250000
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #19:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

999993
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499998
? 2
? 250000
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #20:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

999992
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499997
? 2
? 250000
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #21:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

999991
1
0
1
0
1
0
1
0
1
2
1
2
3
4
3
4
5
6
7
6
7
6
7
6
7
6
7
8
7
8
8

output:

? 1
? 499997
? 2
? 250000
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46879
? 31255
? 39067
? 42973
? 44926
? 42974
? 43950
? 44438
? 44682
? 44804
? 44683
? 44744
? 44684
? 44714
? 44685
? 44700
? 44686
? 44693
? 44697
? 44694
? 44696
! 44696

result:

ok Correct position at 44696

Test #22:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
3

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 16
? 31
? 38
? 42
? 44
! 43

result:

ok Correct position at 43

Test #23:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
1
2
3
2

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 60
? 46
? 53
? 47
? 50
? 52
! 51

result:

ok Correct position at 51

Test #24:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
1
2
3
2

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 60
? 46
? 53
? 47
? 50
? 52
! 51

result:

ok Correct position at 51

Test #25:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

999997
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
2
1
2
3
2

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 60
? 46
? 53
? 47
? 50
? 52
! 51

result:

ok Correct position at 51

Test #26:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
12
13
12
13
12
13
14
13
14
15
15

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 996095
? 998048
? 999025
? 999513
? 999757
? 999879
? 999758
? 999819
? 999759
? 999789
? 999760
? 999775
? 999782
? 999776
? 999779
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

999999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
17
16
17
16

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999971
? 999978
? 999982
? 999979
? 999981
! 999980

result:

ok Correct position at 999980

Test #28:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

999998
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
17
16
17
16

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999970
? 999977
? 999981
? 999978
? 999980
! 999979

result:

ok Correct position at 999979

Test #29:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

999997
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
17
16
17
16

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999969
? 999976
? 999980
? 999977
? 999979
! 999978

result:

ok Correct position at 999978

Test #30:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

1000000
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
14
13
14
13
14
15
14

output:

? 1
? 500001
? 2
? 250002
? 375002
? 437502
? 468752
? 484377
? 492189
? 496095
? 498048
? 499025
? 499513
? 499757
? 499879
? 499940
? 499971
? 499941
? 499956
? 499942
? 499949
? 499943
? 499946
? 499948
! 499947

result:

ok Correct position at 499947

Test #31:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
3
4
5
4
5
5

output:

? 1
? 500001
? 750001
? 500002
? 625002
? 500003
? 562503
? 500004
? 531254
? 500005
? 515630
? 500006
? 507818
? 500007
? 503913
? 500008
? 501961
? 500009
? 500985
? 500010
? 500498
? 500011
? 500255
? 500012
? 500134
? 500013
? 500074
? 500014
? 500044
? 500059
? 500067
? 500071
? 500068
? 500070...

result:

ok Correct position at 500070

Test #32:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
3
2
3
2
3
2
2

output:

? 1
? 500000
? 750000
? 500001
? 625001
? 500002
? 562502
? 500003
? 531253
? 500004
? 515629
? 500005
? 507817
? 500006
? 503912
? 500007
? 501960
? 500008
? 500984
? 500009
? 500497
? 500010
? 500254
? 500011
? 500133
? 500012
? 500073
? 500103
? 500074
? 500089
? 500075
? 500082
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

999997
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
14
15
16
15
16
15

output:

? 1
? 500000
? 2
? 250001
? 375001
? 437501
? 468751
? 484376
? 492188
? 496094
? 498047
? 499024
? 499512
? 499756
? 499878
? 499939
? 499970
? 499940
? 499955
? 499963
? 499967
? 499964
? 499966
! 499965

result:

ok Correct position at 499965

Test #34:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 16
? 31
? 17
? 24
? 18
? 21
? 19
! 19

result:

ok Correct position at 19

Test #35:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 16
? 31
? 17
? 24
? 18
? 21
? 19
! 19

result:

ok Correct position at 19

Test #36:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 16
? 31
? 17
? 24
? 18
? 21
? 19
! 19

result:

ok Correct position at 19

Test #37:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

999997
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7819
? 8
? 3914
? 9
? 1962
? 10
? 986
? 11
? 499
? 12
? 256
? 13
? 135
? 14
? 75
? 15
? 45
? 16
? 31
? 17
? 24
? 18
? 21
? 19
! 19

result:

ok Correct position at 19

Test #38:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

1000000
1
2
3
4
5
6
7
6
7
8
9
8
9
10
11
12
13
12
13
14
13
14
13
14
14

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 984377
? 988283
? 990236
? 991213
? 990237
? 990725
? 990969
? 991091
? 991152
? 991183
? 991153
? 991168
? 991176
? 991169
? 991173
? 991170
? 991172
! 991172

result:

ok Correct position at 991172

Test #39:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
3
4
5
6
7
8
7
8
9
8
9
8
9
9

output:

? 1
? 500001
? 2
? 250002
? 3
? 125003
? 4
? 62504
? 5
? 31255
? 6
? 15631
? 7
? 7819
? 11725
? 13678
? 14655
? 13679
? 14167
? 14411
? 14533
? 14594
? 14625
? 14595
? 14610
? 14618
? 14611
? 14615
? 14612
? 14614
! 14614

result:

ok Correct position at 14614

Test #40:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

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

output:

? 1
? 500000
? 750000
? 500001
? 625001
? 500002
? 562502
? 500003
? 531253
? 500004
? 515629
? 500005
? 507817
? 511723
? 513676
? 514653
? 513677
? 514165
? 514409
? 514531
? 514592
? 514623
? 514593
? 514608
? 514616
? 514609
? 514613
? 514610
? 514612
! 514612

result:

ok Correct position at 514612

Test #41:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

999997
1
0
1
2
1
2
1
2
1
2
1
2
3
4
5
4
5
6
7
8
9
8
9
10
9
10
9
10
10

output:

? 1
? 500000
? 2
? 250001
? 375001
? 250002
? 312502
? 250003
? 281253
? 250004
? 265629
? 250005
? 257817
? 261723
? 263676
? 264653
? 263677
? 264165
? 264409
? 264531
? 264592
? 264623
? 264593
? 264608
? 264616
? 264609
? 264613
? 264610
? 264612
! 264612

result:

ok Correct position at 264612

Test #42:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
19

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992189
? 996095
? 998048
? 999025
? 999513
? 999757
? 999879
? 999940
? 999971
? 999986
? 999994
? 999998
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1000000
0

output:

? 1
! 1

result:

ok Correct position at 1
English 繁體中文 简体中文

Server Time: 2024-12-02 16:04:58 | OpenSource Project