QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136498 | #6394. Turn on the Light | ammardab3an# | WA | 1ms | 3596kb | C++20 | 2.6kb | 2023-08-08 21:33:24 | 2023-08-08 21:33:26 |
Judging History
answer
// By AmmarDab3an
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define ll int64_t
// typedef unsigned int uint;
// typedef long long int ll;
// typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> iii;
typedef pair<ll, pll> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define freopenI freopen("input.txt", "r", stdin);
#define freopenO freopen("output.txt", "w", stdout);
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
int mul(int a, int b){
int ret = (1ll * (a%MOD) * (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int add(int a, int b){
int ret = (1ll * (a%MOD) + (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int pow_exp(int n, int p){
if(!p) return 1;
if(p&1) return mul(n, pow_exp(n, p-1));
int tmp = pow_exp(n, p/2);
return mul(tmp, tmp);
}
int inv(int x){
return pow_exp(x, MOD-2);
}
const int MAX = 2e5 + 10;
const int NMAX = 2e5 + 10;
const int MMAX = 2e5 + 10;
const int LOG_MAX = ceil(log2(double(NMAX)));
const int BLOCK = ceil(sqrt(double(NMAX)));
int fac[NMAX], ifac[NMAX];
void init(){
fac[0] = 1;
for(int i = 1; i < NMAX; i++){
fac[i] = mul(fac[i-1], i);
}
ifac[NMAX-1] = inv(fac[NMAX-1]);
for(int i = NMAX-2; i >= 0; i--){
ifac[i] = mul(ifac[i+1], i+1);
}
}
int choose(int n, int c){
assert(n >= c);
return mul(fac[n], mul(ifac[c], ifac[n-c]));
}
int cnt = 0;
int ask(int x){
cout << "? " << x << endl << flush;
int ret;
cin >> ret;
return ret;
}
int ans(int x){
cout << "! " << x << endl << flush;
exit(0);
}
int32_t main(){
fastIO;
#ifdef LOCAL
freopenI;
freopenO;
#endif
// freopen("name.in", "r", stdin);
// init();
int n;
cin >> n;
int l = 1;
int r = n;
int lst = 0;
while(l < r){
int mid = (l+r)/2;
int a0 = ask(mid);
if(lst==a0){
ans(mid);
}
else{
lst = a0;
}
int a1 = ask(l);
if(lst==a1){
ans(l);
}
else{
if(a1 > a0){
l = mid+1;
}
else{
r = mid-1;
}
lst = a1;
}
}
ans(l);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3436kb
input:
3 1 2
output:
? 2 ? 1 ! 3
result:
ok Correct position at 3
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3596kb
input:
10 1 2 3 4 5 5
output:
? 5 ? 1 ? 8 ? 6 ? 9 ? 9 ! 9
result:
wrong answer Wrong favorite light!