oj.uz

Submission #640577

# Submission time Handle Problem Language Result Execution time Memory
640577 2022-09-15T01:22:32 Z KindaNameless Zagrade (COI20_zagrade) C++14
100 / 100
 892 ms 1192 KB 
#include<algorithm>
#include<iostream>
#include<assert.h>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

bool ask(int a, int b){
    cout << "? " << a << " " << b << "\n"; cout << flush;
    bool ret; cin >> ret;
    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, Q; cin >> N >> Q;

    string s = "";
    vector<int> st;
    vector<bool> valid(N+1);

    for(int i = 1; i <= N; ++i){
        if(st.empty()){
            st.push_back(i);
            s += '(';
            continue;
        }

        bool q = ask(st.back(), i);

        if(q){
            valid[st.back()] = 1;
            valid[i] = 1;
            st.pop_back();
            s += ')';
        }
        else{
            st.push_back(i);
            s += '(';
        }
    }

    assert((int)st.size() % 2 == 0);

    for(int i = 0; i < (int)st.size()/2; ++i){
        s[st[i]-1] = ')';
    }

    cout << "! " << s << "\n"; cout << flush;

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 7 ms 208 KB Output is correct
4 Correct 8 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 8 ms 316 KB Output is correct
3 Correct 9 ms 316 KB Output is correct
4 Correct 5 ms 316 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 9 ms 316 KB Output is correct
8 Correct 6 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 288 ms 552 KB Output is correct
3 Correct 759 ms 620 KB Output is correct
4 Correct 725 ms 648 KB Output is correct
5 Correct 673 ms 652 KB Output is correct
6 Correct 745 ms 712 KB Output is correct
7 Correct 813 ms 804 KB Output is correct
8 Correct 698 ms 576 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 592 ms 1192 KB Output is correct
3 Correct 613 ms 780 KB Output is correct
4 Correct 860 ms 1040 KB Output is correct
5 Correct 702 ms 920 KB Output is correct
6 Correct 892 ms 828 KB Output is correct
7 Correct 569 ms 668 KB Output is correct
8 Correct 703 ms 712 KB Output is correct