QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588805#6394. Turn on the Lightyumingsk#TL 0ms3636kbC++141.3kb2024-09-25 14:38:482024-09-25 14:38:49

Judging History

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

  • [2024-09-25 14:38:49]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3636kb
  • [2024-09-25 14:38:48]
  • 提交

answer

#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";

using namespace std;
const int Mod = 998244353;
using ll = long long;
int fh = 0;
int print(int x)
{
    cout << "? " << x << endl;
    int c;
    cin >> c;
    return c - fh;
}
int f(int l, int r)
{
    // cout << l << ' ' << r << '\n';
    if (l == r)
        return l;
    int num = 0;
    int ttt = 1;
    int i;
    for (i = l; i <= r; i += ttt)
    {
        ttt *= 2;
        int nxt = print(i);
        // cout << l << ' ' << r << ' ' << i << ' ' << ttt << '\n';
        num++;
        if (nxt == num)
            continue;
        else if (nxt == num - 1)
        {
            return i;
        }
        else
        {
            fh += nxt;
            if (i - ttt / 2 <= i)
                return f(i - ttt / 2, i);
        }
    }
    // cout << i << ' ' << ttt << '\n';
    if (i - ttt + 1 <= r)
        return f(i - ttt, r);
}
void solve()
{
    int n;
    cin >> n;
    int res = f(1, n);
    cout << "! " << res << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

3
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: -100
Time Limit Exceeded

input:

10
1
2
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4...

output:

? 1
? 3
? 7
? 7
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
? 6
...

result: