Submission #680564

#	Time	Username	Problem	Language	Result	Execution time	Memory
680564		Cross_Ratio	Colors (BOI20_colors)	C++14	100 / 100	3 ms	336 KiB

Colors

#include <bits/stdc++.h>
#define int long long
using namespace std;
int point(int k) {
    if(k==1) return 1;
    if(k==2) return 2;
    if(k==3) return 2;
    if(k==4) return 3;
    if(k==5) return 4;
    if(k==6) return 5;
    if(k%2==0) {
        int n = k / 2;
        int p = point(n);
        if(p < (n+1)/2) {
            return p + n;
        }
        return p;
    }
    int n = k/2;
    int p = point(n+1);
    if(p < (n+2)/2) {
        return p + n;
    }
    return p;
}
vector<bool> res;
vector<int> cnt;
void answer(int c) {
    cout << "= " << c << endl;
}
bool query(int c) {
    cout << "? " << c << endl;
    bool k;
    cin >> k;
    return k;
}
signed main() {



    int N;
    cin >> N;
    int i, j;
    int p = point(N);
    if(N==1) {
        answer(1);
        return 0;
    }
    query(p);
    int d = (N+1)/2;
    int rev = 0;
    if(p+d<=N) {
        rev = 1;
    }
    else rev = 0;
    int ans = 0;
    while(true) {
        //cout << "Current N is " << N << '\n';
        if(N==1) {
            answer(ans+1);
            return 0;
        }
        int d = N / 2 + ans;
        if(rev) p += d;
        else p -= d;
        bool k = query(p);
        rev = 1 - rev;
        if(k) N = N / 2;
        else {
            ans += N / 2;
            N = N - N / 2;
        }
    }
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:43:9: warning: unused variable 'i' [-Wunused-variable]
   43 |     int i, j;
      |         ^
Colors.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
   43 |     int i, j;
      |            ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 33 / 33