oj.uz

Submission #988345

# Submission time Handle Problem Language Result Execution time Memory
988345 2024-05-24T14:22:16 Z fanwen Zagrade (COI20_zagrade) C++17
100 / 100
 507 ms 1944 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define fi first
#define se second
#define REP(i, n) for (auto i = 0; i < (n); ++i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (auto i = (a); i >= (b); --i)
#define FORE(i, a, b) for (auto i = (a); i < (b); ++i)
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define left ___left 
#define right ___right 
#define __builtin_popcount __builtin_popcountll

const int MAX = 1e5 + 5; 

int n, q, a[MAX];

int ask (int l, int r) {
    cout << "? " << l << " " << r << endl;
    int x; cin >> x; return x; 
}

void you_make_it(void) {
    cin >> n >> q; 
    deque <int> dq; 
    fill(a + 1, a + n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        if(i > 1 and !dq.empty()) {
            if(ask(dq.back(), i)) {
                a[dq.back()] = 0;
                a[i] = 1;
                dq.pop_back();
            } else {
                dq.push_back(i);
            }
        } else {
            dq.push_back(i);
        }
    }

    for (int i = 0; i < dq.size() / 2; ++i) {
        a[dq[i]] = 1;
        a[dq[dq.size() - i - 1]] = 0;
    }
    cout << "! ";
    for (int i = 1; i <= n; ++i) {
        assert(a[i] != -1);
        cout << (a[i] ? ")" : "(");
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif // LOCAL
    auto start_time = chrono::high_resolution_clock::now();

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
    // cin >> test;

    for (int i = 0; i < test; ++i) {
        you_make_it();
        // cout << '\n';
    }
    auto end_time = chrono::high_resolution_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

zagrade.cpp: In function 'void you_make_it()':
zagrade.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < dq.size() / 2; ++i) {
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 4 ms 868 KB Output is correct
8 Correct 4 ms 600 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 4 ms 464 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 212 ms 828 KB Output is correct
3 Correct 466 ms 828 KB Output is correct
4 Correct 485 ms 828 KB Output is correct
5 Correct 455 ms 824 KB Output is correct
6 Correct 507 ms 828 KB Output is correct
7 Correct 463 ms 1720 KB Output is correct
8 Correct 487 ms 820 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 432 ms 1764 KB Output is correct
3 Correct 461 ms 1660 KB Output is correct
4 Correct 480 ms 1944 KB Output is correct
5 Correct 437 ms 1668 KB Output is correct
6 Correct 441 ms 1752 KB Output is correct
7 Correct 474 ms 1440 KB Output is correct
8 Correct 476 ms 820 KB Output is correct