QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378540 | #6394. Turn on the Light | Destiny# | TL | 0ms | 0kb | C++14 | 2.5kb | 2024-04-06 13:29:51 | 2024-04-06 13:29:52 |
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;
int n;
ll p;
ll last;
void input()
{
last = p;
cin >> p;
}
void out(ll u)
{
cout << "? " << u << flush;
}
bool check()
{
}
bool ans(ll u){
cout << "! " << u << flush;
}
void solve()
{
cin >> n;
if (n == 1)
{
ans(1);
return;
}
ll l = 1, r = n, x = 1, y = n;
ll mid = l + r >> 1;
out(mid);
input();
if (p == last)
{
ans(mid);
return;
}
r = mid;
// x = mid + 1;
while(1){
// cout << "l r = " << l << ' ' << r << endl;
mid = l + r >> 1;
out(mid);
input();
if(last == p){
ans(mid);
return;
}else if(p < last){
if(mid > y / 2){
r = mid;
}else {
l = mid;
}
n = r;
// mid = l + r >> 1;
// out(mid);
// input();
}else {
ll midx = n - mid + 1;
out(midx);
input();
if(last == p){
ans(midx);
return;
}else if(last > p){
l = n - r + 1, r = midx;
n = r;
}else {
r = mid;
}
}
}
return;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3
output:
? 2