oj.uz

Submission #1096916

# Submission time Handle Problem Language Result Execution time Memory
1096916 2024-10-05T12:31:47 Z gyg Colors (BOI20_colors) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db long double

int n;

bool qry(int x) {
    cout << "? " << x << endl;
    bool ans; cin >> ans;
    return ans;
}

bool chck(int st) {
    int ps = st, drc = -1;
    int lw = 1, hg = n;
    while (lw != hg) {
        int md = (lw + hg) / 2;
        ps += drc * md;
        if (ps < 1 || n < ps) return false;
        lw = md + 1;
        drc *= -1;
    }
    return true;
}
int gt_st() {
    int st = roundl(n * (db) 2 / 3);
    for (int i = st - 100; i <= st + 100; i++)
        if (chck(i)) return i;
    assert(false);
}

int bn_srch(int st) {
    int ps = st; qry(ps);
    int add = 0, drc = -1, lw = 1, hg = n;
    while (lw != hg) {
        int hlf = (hg - lw + 1) / 2;
        ps += drc * (hlf + add);
        if (qry(ps)) hg = lw + hlf - 1;
        else {
            add += hlf;
            lw = lw + hlf;
        }
        drc *= -1;
    }
    return lw;
}

signed main() {
    cin >> n;

    int ans = bn_srch(gt_st());
    cout << "= " << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -