oj.uz

Submission #552059

# Submission time Handle Problem Language Result Execution time Memory
552059 2022-04-22T11:02:32 Z hoanghq2004 Colors (BOI20_colors) C++14
0 / 100
 0 ms 208 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        long long minv = 0;
        long long L = 1, R = n - 1;
        long long cur = 0;
        int sign = 1;
        while (L <= R) {
            long long mid = L + R >> 1;
            cur += sign * mid;
            minv = min(minv, cur);
            sign *= -1;
            L = mid + 1;
        }
        cur = 1 - minv;
        sign = 1;
        set <long long> s;
        auto ask = [&](long long x) {
            cout << "? " << x << endl;
            s.insert(x);
            string ans;
            cin >> ans;
            return (ans == "YES");
        };
        ask(cur);
        L = 1, R = n - 1;
        long long ans = n;
        while (L <= R) {
            long long mid = L + R >> 1;
            cur += sign * mid;
            sign *= -1;
            if (ask(cur)) R = mid - 1, ans = min(ans, mid);
            else L = mid + 1;
        }
        cout << "= " << ans << endl;
    }
}

Compilation message

Colors.cpp: In function 'int main()':
Colors.cpp:27:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             long long mid = L + R >> 1;
      |                             ~~^~~
Colors.cpp:47:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             long long mid = L + R >> 1;
      |                             ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -