QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218030 | #6394. Turn on the Light | CRN2010 | WA | 1ms | 3716kb | C++20 | 1.3kb | 2023-10-17 17:30:36 | 2023-10-17 17:30:36 |
Judging History
answer
#include <bits/stdc++.h>
#define int unsigned long long
#define ls (x << 1)
#define rs (x << 1 | 1 )
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(x,y,z) for(int x = (y) ; x <= z ; ++x )
#define FOR_(x,y,z) for(int x = (y) ; x >= z ; --x )
#define all(x) x.begin(),x.end()
//#define endl '\n'
const int N = 1e5+5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
using namespace std;
inline int read() {
int ans=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+(ch^48);ch=getchar();}
return ans*f;
}
void write(int x) {
if(x<0){putchar('-');x=-1;}
if(x>9){write(x/10);}
putchar(x%10|48);
}
void solve() {
int n , pre , now ;
n = read() ;
cout << "? 1" << endl;
pre = read() ;
if ( pre == 0 ) {
cout << "! 1" << endl;
return ;
}
int left = 1 , right = n ;
if( n == 2 ) ++left ;
while(right >= left) {
int mid = (right+left)>>1;
cout << "? "<<mid<< endl ;
now = read() ;
if ( now == pre ) {
cout << "! " << mid << endl ;
break ;
}
else if ( now > pre ) {
left = mid + 1 ;
}
else {
right = mid - 1 ;
}
pre = now ;
}
}
signed main()
{
int t = 1 ;
// t = read() ;
while(t -- ) {
solve() ;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
3 1 2 2
output:
? 1 ? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
10 1 2 3 3
output:
? 1 ? 5 ? 8 ? 9 ! 9
result:
ok Correct position at 9
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
9 1 2 3 3
output:
? 1 ? 5 ? 7 ? 8 ! 8
result:
ok Correct position at 8
Test #4:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
8 1 2 3 3
output:
? 1 ? 4 ? 6 ? 7 ! 7
result:
ok Correct position at 7
Test #5:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
7 1 2 3 3
output:
? 1 ? 4 ? 6 ? 7 ! 7
result:
ok Correct position at 7
Test #6:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
6 1 2 3 3
output:
? 1 ? 3 ? 5 ? 6 ! 6
result:
ok Correct position at 6
Test #7:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
5 1 2 3 3
output:
? 1 ? 3 ? 4 ? 5 ! 5
result:
ok Correct position at 5
Test #8:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
4 1 2 3 3
output:
? 1 ? 2 ? 3 ? 4 ! 4
result:
ok Correct position at 4
Test #9:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
3 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #10:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
2 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #11:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
1 0
output:
? 1 ! 1
result:
ok Correct position at 1
Test #12:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1000000 1 2 3 4 5 6 7 6 7 8 7 8 9 10 11 12 13 14 15 16 16
output:
? 1 ? 500000 ? 750000 ? 875000 ? 937500 ? 968750 ? 984375 ? 992188 ? 988281 ? 990234 ? 991211 ? 990722 ? 990966 ? 991088 ? 991149 ? 991180 ? 991195 ? 991203 ? 991207 ? 991209 ? 991210 ! 991210
result:
ok Correct position at 991210
Test #13:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
999999 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12 12
output:
? 1 ? 500000 ? 750000 ? 875000 ? 812500 ? 843750 ? 828125 ? 820312 ? 824218 ? 826171 ? 827148 ? 826659 ? 826903 ? 827025 ? 827086 ? 827117 ? 827132 ? 827140 ? 827144 ? 827146 ? 827147 ! 827147
result:
ok Correct position at 827147
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
999998 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12 12
output:
? 1 ? 499999 ? 749999 ? 874999 ? 812499 ? 843749 ? 828124 ? 820311 ? 824217 ? 826170 ? 827147 ? 826658 ? 826902 ? 827024 ? 827085 ? 827116 ? 827131 ? 827139 ? 827143 ? 827145 ? 827146 ! 827146
result:
ok Correct position at 827146
Test #15:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
999997 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12 12
output:
? 1 ? 499999 ? 749998 ? 874998 ? 812498 ? 843748 ? 828123 ? 820310 ? 824216 ? 826169 ? 827146 ? 826657 ? 826901 ? 827023 ? 827084 ? 827115 ? 827130 ? 827138 ? 827142 ? 827144 ? 827145 ! 827145
result:
ok Correct position at 827145
Test #16:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
999996 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12 12
output:
? 1 ? 499998 ? 749997 ? 874997 ? 812497 ? 843747 ? 828122 ? 820309 ? 824215 ? 826168 ? 827145 ? 826656 ? 826900 ? 827022 ? 827083 ? 827114 ? 827129 ? 827137 ? 827141 ? 827143 ? 827144 ! 827144
result:
ok Correct position at 827144
Test #17:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
999995 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14 14
output:
? 1 ? 499998 ? 749997 ? 874996 ? 937496 ? 968746 ? 953121 ? 945308 ? 949214 ? 951167 ? 952144 ? 951655 ? 951899 ? 952021 ? 952082 ? 952113 ? 952128 ? 952136 ? 952140 ? 952142 ? 952143 ! 952143
result:
ok Correct position at 952143
Test #18:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
999994 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14 14
output:
? 1 ? 499997 ? 749996 ? 874995 ? 937495 ? 968745 ? 953120 ? 945307 ? 949213 ? 951166 ? 952143 ? 951654 ? 951898 ? 952020 ? 952081 ? 952112 ? 952127 ? 952135 ? 952139 ? 952141 ? 952142 ! 952142
result:
ok Correct position at 952142
Test #19:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
999993 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14 14
output:
? 1 ? 499997 ? 749995 ? 874994 ? 937494 ? 968744 ? 953119 ? 945306 ? 949212 ? 951165 ? 952142 ? 951653 ? 951897 ? 952019 ? 952080 ? 952111 ? 952126 ? 952134 ? 952138 ? 952140 ? 952141 ! 952141
result:
ok Correct position at 952141
Test #20:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
999992 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14 14
output:
? 1 ? 499996 ? 749994 ? 874993 ? 937493 ? 968743 ? 953118 ? 945305 ? 949211 ? 951164 ? 952141 ? 951652 ? 951896 ? 952018 ? 952079 ? 952110 ? 952125 ? 952133 ? 952137 ? 952139 ? 952140 ! 952140
result:
ok Correct position at 952140
Test #21:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
999991 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12 12
output:
? 1 ? 499996 ? 749994 ? 874993 ? 812493 ? 843743 ? 828118 ? 820305 ? 824211 ? 826164 ? 827141 ? 826652 ? 826896 ? 827018 ? 827079 ? 827110 ? 827125 ? 827133 ? 827137 ? 827139 ? 827140 ! 827140
result:
ok Correct position at 827140
Test #22:
score: -100
Wrong Answer
time: 1ms
memory: 3684kb
input:
1000000 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
output:
? 1 ? 500000 ? 250000 ? 375000 ? 437500 ? 468750 ? 484375 ? 492187 ? 496093 ? 498046 ? 499023 ? 499511 ? 499755 ? 499877 ? 499938 ? 499969 ? 499984 ? 499992 ? 499996 ? 499998 ? 499999
result:
wrong answer format Unexpected end of file - token expected