Cod sursa(job #3147179)

Utilizator nnmadalinNeauna Madalin nnmadalin Data 24 august 2023 14:57:02
Problema Cbinteractiv Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define int long long 

//#define cin fin
//#define cout fout

const string FILE_NAME = "data";
ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");

vector<int> lps(string a){
    vector <int> v(a.size(), 0);

    int len = 0;
    
    for(int i = 1; i < a.size();){
        if(a[i] == a[len]){
            len++;
            v[i] = len;
            i++;
        }
        else{
            if(len != 0){
                len = v[len - 1];
            }
            else
                v[i] = 0, i++;
        }
    }

    return v;
}

signed main()
{
    int n, st = 1, dr = n;

    cin >> n;

    dr = n;

    while(st <= dr){
        int mid = (st + dr) / 2;
        cout << "? " << mid << "\n";
        cout.flush();
        int k; cin >> k;
        if(k == 1)
            dr = mid - 1;
        else if(k == 0)
            st = mid + 1;
        else
            return 0;
    }

    cout << "! " << (st + dr) / 2 + 1;
    
    return 0;
}