| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 999770 |
2024-06-16T06:38:29 Z |
Gray |
Colors (BOI20_colors) |
C++17 |
|
0 ms |
344 KB |
#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll MOD = (ll)1e9+7;
const ll INF = 2e18;
vector<ll> fact(1001);
ll binpow(ll a, ll b){
if (!b) return 1;
ll res=binpow(a, b/2);
res=res*res%MOD;
if (b%2) res=res*a%MOD;
return res;
}
ll inv(ll x){
return binpow(x, MOD-2);
}
ll bin(ll n, ll k){
return fact[n]*inv(fact[n-k]*fact[k]%MOD)%MOD;
}
void gen(){
fact[0]=1;
for (ll i=1; i<=1000; i++){
fact[i]=fact[i-1]*i%MOD;
}
}
void solve(){
ll n; cin >> n;
ll rem = n%2;
n-=rem;
map<ll, ll> usd;
ll l=0, r=n;
ll prev=-1;
while (l+2<r){
ll mid = (l+r)/2;
mid-=!(mid%2);
cout << mid << endl;
if (usd[mid]) mid+=2;
assert(!usd[mid]);
usd[mid]=1;
ll f = n/2+mid/2+1, s = n/2-mid/2;
cout << "? " << f << endl;
ll x; cin >> x;
if (prev>-1){
if (x){
r=min(r, abs(prev-f));
}else{
l=max(l, abs(prev-f));
}
}
cout << "? " << s << endl;
cin >> x;
if (x){
r=min(mid, r);
}else{
l=max(l, mid);
}
prev=s;
}
if (l+1<r){
ll mid=l+1;
assert(prev+mid<=n);
cout << "? " << prev+mid << endl;
ll x; cin >> x;
if (x) r=l+1;
}
if (r==n and rem){
cout << "? " << n+rem << endl;
ll x; cin >> x;
if (!x) r=n+1;
}
cout <<"= " << r << ln;
}
// 0 0 1 x 1 1 1 1 0 0
int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
