QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378649#6394. Turn on the LightDestiny#AC ✓1ms3960kbC++142.2kb2024-04-06 13:59:102024-04-06 13:59:11

Judging History

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

  • [2024-04-06 13:59:11]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3960kb
  • [2024-04-06 13:59:10]
  • 提交

answer

// #define NDEBUG
#include <bits/stdc++.h>

using namespace std;
namespace LIN
{
#if defined(LOCAL) and not defined(ONLINE_JUDGE)
#include "C:\Users\ushop\Desktop\CodeFile\CODE_C++\vscode\LOCAL\debug.h"
#define DBG(X) cout << #X " = " << X << endl
#else
#define dbg(...) ;
#define DBG(...) ;
#endif
	using ll = long long;
	using db = double;
	// using LL = __int128;
	// using ldb = long double;

	// void print(LL x)
	//{
	// if (x < 0)
	//{
	// x = -x;
	// putchar('-');
	//}
	// if (x > 9)
	// print(x / 10);
	// putchar(x % 10 + '0');
	//}

	ll fast(ll u, ll v, ll p)
	{
		ll res = 1;
		while (v)
		{
			if (v & 1)
				res = res * u % p;
			v >>= 1;
			u = u * u % p;
		}
		return res;
	}

#define SPO(X) fixed << setprecision(X)
#define fo(i, l, r) for (ll i = l; i <= r; i++)
#define of(i, r, l) for (ll i = r; i >= l; i--)
#define inf(u, p) fast(u, p - 2, p)
#define edl '\n'
#define HEAP priority_queue
#define PII pair<ll, ll>
#define PIIL pair<PII, ll>
#define PIIR pair<ll, PII>
#define F first
#define S second
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
#define ANS() cout << ans << endl

	constexpr int N = 1e6 + 10;
	constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;
	constexpr db EPS = 1.0e-9;
	constexpr ll MOD = 1e9 + 7;
	constexpr ll SZ = 1e5 + 5;

}
using namespace LIN;
// #define ll int
int n;
int p;
int last;

void out(int u)
{
	last = p;
	printf("? %d\n", u);fflush(stdout);scanf("%d", &p);
}

void ans(int u){
	printf("! %d\n", u);
    fflush(stdout);
}

void solve()
{
	scanf("%d", &n);

	int l = 1, r = n, x = 1, y = n;

	while(1){
		// cout << "l r = " << l << ' ' << r << endl;
		out(l);
		if(last == p){
			ans(l);
			return;
		}
		l ++;
		while(l < r){
			int mid = l + r >> 1;
			out(mid);
			if(last == p) {
				ans(mid);
				return;
			} 
			if(last > p){
				r = mid - 1;	
				break;
			}else {
				l = mid + 1;
			}
		}
		if(l == r) {
			ans(l);
			return;
		}
	}

	return;
}

int main()
{
	// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int T = 1;
	// cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}

详细

Test #1:

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

input:

3
1
2

output:

? 1
? 2
! 3

result:

ok Correct position at 3

Test #2:

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

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: 3892kb

input:

9
1
2
3
3

output:

? 1
? 5
? 7
? 8
! 8

result:

ok Correct position at 8

Test #4:

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

input:

8
1
0
1
1

output:

? 1
? 5
? 2
? 3
! 3

result:

ok Correct position at 3

Test #5:

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

input:

7
1
2
3

output:

? 1
? 4
? 6
! 7

result:

ok Correct position at 7

Test #6:

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

input:

6
1
0
1

output:

? 1
? 4
? 2
! 3

result:

ok Correct position at 3

Test #7:

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

input:

5
1
2
3

output:

? 1
? 3
? 4
! 5

result:

ok Correct position at 5

Test #8:

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

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

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

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

input:

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

output:

? 1
? 500001
? 2
? 250001
? 375001
? 437501
? 375002
? 406251
? 421876
? 406252
? 414064
? 406253
? 410158
? 412111
? 413087
? 413575
? 413819
? 413941
? 414002
? 414033
? 414003
? 414018
? 414004
? 414011
? 414005
? 414008
? 414009
! 414010

result:

ok Correct position at 414010

Test #13:

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

input:

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

output:

? 1
? 500000
? 750000
? 875000
? 750001
? 812500
? 843750
? 812501
? 828125
? 835937
? 839843
? 841796
? 842773
? 843261
? 843505
? 843627
? 843688
? 843719
? 843734
? 843742
? 843735
? 843738
? 843740
! 843740

result:

ok Correct position at 843740

Test #14:

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

input:

999998
1
0
1
0
1
0
1
0
1
2
3
4
5
6
5
6
7
8
9
8
9
8
9
10
11
12
12

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 46878
? 54690
? 58596
? 60549
? 61526
? 60550
? 61038
? 61282
? 61404
? 61465
? 61405
? 61435
? 61406
? 61420
? 61427
? 61431
? 61433
! 61433

result:

ok Correct position at 61433

Test #15:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 749999
? 812498
? 843748
? 812499
? 828123
? 835935
? 839841
? 841794
? 842771
? 843259
? 843503
? 843625
? 843686
? 843717
? 843732
? 843740
? 843733
? 843736
? 843738
! 843738

result:

ok Correct position at 843738

Test #16:

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

input:

999996
1
0
1
2
3
2
3
4
3
4
3
4
5
6
7
8
9
10
11
10
11
10
11
10
11
12
13

output:

? 1
? 499999
? 2
? 250000
? 374999
? 437499
? 375000
? 406249
? 421874
? 406250
? 414062
? 406251
? 410156
? 412109
? 413085
? 413573
? 413817
? 413939
? 414000
? 414031
? 414001
? 414016
? 414002
? 414009
? 414003
? 414006
? 414007
! 414008

result:

ok Correct position at 414008

Test #17:

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

input:

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

output:

? 1
? 499998
? 749997
? 874996
? 937496
? 968746
? 937497
? 953121
? 960933
? 964839
? 966792
? 967769
? 966793
? 967281
? 967525
? 967282
? 967403
? 967464
? 967494
? 967509
? 967517
? 967510
? 967513
? 967515
! 967514

result:

ok Correct position at 967514

Test #18:

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

input:

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

output:

? 1
? 499998
? 2
? 250000
? 3
? 125001
? 187500
? 218750
? 187501
? 203125
? 210937
? 214843
? 216796
? 217773
? 218261
? 218505
? 218627
? 218688
? 218719
? 218734
? 218742
? 218735
? 218738
? 218740
! 218739

result:

ok Correct position at 218739

Test #19:

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

input:

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

output:

? 1
? 499997
? 749995
? 874994
? 937494
? 968744
? 937495
? 953119
? 960931
? 964837
? 966790
? 967767
? 966791
? 967279
? 967523
? 967280
? 967401
? 967462
? 967492
? 967507
? 967515
? 967508
? 967511
? 967513
! 967512

result:

ok Correct position at 967512

Test #20:

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

input:

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

output:

? 1
? 499997
? 2
? 249999
? 374998
? 437497
? 468747
? 437498
? 453122
? 460934
? 464840
? 466793
? 467770
? 468258
? 468502
? 468624
? 468685
? 468716
? 468731
? 468739
? 468732
? 468735
? 468737
! 468737

result:

ok Correct position at 468737

Test #21:

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

input:

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

output:

? 1
? 499996
? 749994
? 874993
? 749995
? 812494
? 749996
? 781245
? 749997
? 765621
? 773433
? 765622
? 769527
? 771480
? 772456
? 772944
? 773188
? 773310
? 773371
? 773402
? 773372
? 773387
? 773373
? 773380
? 773374
? 773377
? 773378
! 773379

result:

ok Correct position at 773379

Test #22:

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

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
5

output:

? 1
? 500001
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 16
? 30
? 37
? 40
? 42
! 43

result:

ok Correct position at 43

Test #23:

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

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
4

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #24:

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

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
4

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #25:

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

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
4

output:

? 1
? 499999
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7818
? 8
? 3913
? 9
? 1961
? 10
? 985
? 11
? 498
? 12
? 255
? 13
? 134
? 14
? 74
? 15
? 44
? 59
? 45
? 52
? 46
? 49
? 50
! 51

result:

ok Correct position at 51

Test #26:

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

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999757
? 999817
? 999758
? 999787
? 999759
? 999773
? 999780
? 999783
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

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

input:

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

output:

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

result:

ok Correct position at 999980

Test #28:

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

input:

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

output:

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

result:

ok Correct position at 999979

Test #29:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999968
? 999975
? 999978
! 999978

result:

ok Correct position at 999978

Test #30:

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

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
16

output:

? 1
? 500001
? 2
? 250001
? 375001
? 437501
? 468751
? 484376
? 492188
? 496094
? 498047
? 499024
? 499512
? 499756
? 499878
? 499939
? 499970
? 499940
? 499955
? 499941
? 499948
? 499942
? 499945
? 499946
! 499947

result:

ok Correct position at 499947

Test #31:

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

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
6
6

output:

? 1
? 500000
? 750000
? 500001
? 625000
? 500002
? 562501
? 500003
? 531252
? 500004
? 515628
? 500005
? 507816
? 500006
? 503911
? 500007
? 501959
? 500008
? 500983
? 500009
? 500496
? 500010
? 500253
? 500011
? 500132
? 500012
? 500072
? 500013
? 500042
? 500057
? 500064
? 500068
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

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
3
2

output:

? 1
? 500000
? 749999
? 500001
? 625000
? 500002
? 562501
? 500003
? 531252
? 500004
? 515628
? 500005
? 507816
? 500006
? 503911
? 500007
? 501959
? 500008
? 500983
? 500009
? 500496
? 500010
? 500253
? 500011
? 500132
? 500012
? 500072
? 500102
? 500073
? 500087
? 500074
? 500080
? 500075
? 500077...

result:

ok Correct position at 500076

Test #33:

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

input:

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

output:

? 1
? 499999
? 2
? 250000
? 374999
? 437499
? 468749
? 484374
? 492186
? 496092
? 498045
? 499022
? 499510
? 499754
? 499876
? 499937
? 499968
? 499938
? 499953
? 499960
? 499964
? 499966
! 499965

result:

ok Correct position at 499965

Test #34:

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

input:

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

output:

? 1
? 500001
? 2
? 250001
? 375001
? 250002
? 312501
? 343751
? 312502
? 328126
? 335938
? 339844
? 341797
? 342774
? 341798
? 342286
? 341799
? 342042
? 342164
? 342043
? 342103
? 342133
? 342148
? 342156
? 342149
? 342152
? 342154
! 342153

result:

ok Correct position at 342153

Test #35:

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

input:

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

output:

? 1
? 500000
? 750000
? 500001
? 625000
? 687500
? 625001
? 656250
? 671875
? 656251
? 664063
? 656252
? 660157
? 662110
? 660158
? 661134
? 660159
? 660646
? 660890
? 660647
? 660768
? 660829
? 660769
? 660799
? 660770
? 660784
? 660791
? 660795
? 660792
? 660793
! 660793

result:

ok Correct position at 660793

Test #36:

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

input:

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

output:

? 1
? 500000
? 2
? 250001
? 3
? 125002
? 4
? 62503
? 5
? 31254
? 6
? 15630
? 7
? 7818
? 11724
? 7819
? 9771
? 10747
? 11235
? 11479
? 11601
? 11662
? 11693
? 11663
? 11678
? 11664
? 11671
? 11665
? 11668
? 11666
! 11666

result:

ok Correct position at 11666

Test #37:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 749999
? 812498
? 843748
? 812499
? 828123
? 835935
? 839841
? 841794
? 842771
? 841795
? 842283
? 841796
? 842039
? 842161
? 842040
? 842100
? 842130
? 842145
? 842153
? 842146
? 842149
? 842151
! 842150

result:

ok Correct position at 842150

Test #38:

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

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #39:

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

input:

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

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999992
? 999996
? 999998
! 999999

result:

ok Correct position at 999999

Test #40:

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

input:

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

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999991
? 999995
? 999997
! 999998

result:

ok Correct position at 999998

Test #41:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999990
? 999994
? 999996
! 999997

result:

ok Correct position at 999997

Test #42:

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

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
0

output:

? 1
! 1

result:

ok Correct position at 1