oj.uz

Submission #334042

# Submission time Handle Problem Language Result Execution time Memory
334042 2020-12-08T07:28:50 Z limabeans Zagrade (COI20_zagrade) C++17
100 / 100
 961 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n, q;
char ans[maxn];


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



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

    cin>>n>>q;


    vector<int> stk;
    for (int i=0; i<n; i++) {
	if (stk.empty()) {
	    stk.push_back(i);
	    continue;
	}
	int res = ask(stk.back(), i);
	if (res==1) {
	    ans[stk.back()]='(';
	    ans[i]=')';
	    stk.pop_back();
	} else {
	    stk.push_back(i);
	}
    }

    int len = stk.size();
    assert(len%2==0);
    for (int i=0; i<len; i++) {
	if (i<len/2) {
	    ans[stk[i]]=')';
	} else {
	    ans[stk[i]]='(';
	}
    }

    cout<<"! ";
    for (int i=0; i<n; i++) {
	cout<<ans[i];
    }
    cout<<endl;
    
    
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 10 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 12 ms 364 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 7 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 11 ms 364 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 9 ms 364 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 9 ms 364 KB Output is correct
8 Correct 9 ms 364 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 458 ms 628 KB Output is correct
3 Correct 738 ms 688 KB Output is correct
4 Correct 778 ms 768 KB Output is correct
5 Correct 756 ms 620 KB Output is correct
6 Correct 626 ms 620 KB Output is correct
7 Correct 829 ms 752 KB Output is correct
8 Correct 695 ms 816 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 879 ms 1400 KB Output is correct
3 Correct 819 ms 1004 KB Output is correct
4 Correct 685 ms 968 KB Output is correct
5 Correct 961 ms 912 KB Output is correct
6 Correct 683 ms 908 KB Output is correct
7 Correct 782 ms 1004 KB Output is correct
8 Correct 797 ms 800 KB Output is correct