oj.uz

Submission #255905

# Submission time Handle Problem Language Result Execution time Memory
255905 2020-08-02T05:21:54 Z 반딧불(#5032) Colors (BOI20_colors) C++17
0 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;
set<ll> st;

ll findStartLoc(ll x){
    ll l = 1, r = n-1;
    stack<ll> stk;
    while(l <= r){
        ll m = (l+r)>>1;
        stk.push(m);
        l = m+1;
    }
    ll ret = 1;
    bool tmp = 0;
    while(!stk.empty()){
        if(!tmp) ret += stk.top();
        else ret -= stk.top();
        tmp = !tmp;
        stk.pop();
    }
    return ret;
}

int qc;
bool noticed(ll x){
    qc++;
    if(qc > 64){
        exit(1);
    }
    st.insert(x);
    printf("? %lld\n", x);
    fflush(stdout);
    bool ret;
    scanf("%d", &ret);
    return ret;
}

int main(){
    scanf("%lld", &n);
    ll startLoc = findStartLoc(n);

    noticed(startLoc);
    ll curr = startLoc;
    ll l = 1, r = n-1;
    ll ans = n;

    while(l <= r){
        ll m = (l+r)>>1;
        ll queryLoc;
        if(curr > m){
            queryLoc = curr - m;
        }
        else if(curr + m <= n){
            queryLoc = curr + m;
        }
        else{
            queryLoc = 1;
            while(st.find(queryLoc) != st.end()) queryLoc++;
            noticed(queryLoc);
            continue;
        }

        if(noticed(queryLoc)){
            ans = m;
            r = m-1;
        }
        else{
            l = m+1;
        }
        curr = queryLoc;
    }
    printf("= %lld\n", ans);
    fflush(stdout);
    return 0;
}

Compilation message

Colors.cpp: In function 'bool noticed(ll)':
Colors.cpp:39:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
     scanf("%d", &ret);
                 ~~~~^
Colors.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ret);
     ~~~~~^~~~~~~~~~~~
Colors.cpp: In function 'int main()':
Colors.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -