oj.uz

Submission #312755

# Submission time Handle Problem Language Result Execution time Memory
312755 2020-10-14T09:58:40 Z AmineTrabelsi Zagrade (COI20_zagrade) C++14
100 / 100
 973 ms 1200 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) ((int)x.size())
const ll maxint=2e18;
const ll minint =-2e18;

// Hi
bool ask(int i,int j){
	bool response;
	cout << "? "<<i+1<<" "<<j+1<< endl;
    cin >> response;
    return response;
}
int main(){
	sync
	int n, q;
    cin >> n >> q;
    vector<int> st;
    vector<char> res(n,'-');
    for(int i=0;i<n;i++){
    	if(st.empty()){
    		st.pb(i);
    		continue;
    	}
    	int last = st.back();
    	bool r = ask(last,i);
    	if(r){
    		st.pop_back();
    		res[last]= '(';
    		res[i]=')';
    	}else{
    		st.pb(i);
    	}
    }
    if(!st.empty()){
    	int x = sz(st);
    	int to = x/2;
    	if(x&1)to--;
    	while(!st.empty() && to){
    		res[st.back()] = '(';
    		st.pop_back();
    		to--;
    	}
    	while(!st.empty()){
    		res[st.back()] = ')';
    		st.pop_back();
    	}
    }
    cout<<"! ";
    for(auto i:res)cout<<i;
    	cout<<endl;
    
	return 0;
}
/*
3
())
*/

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 388 ms 504 KB Output is correct
3 Correct 950 ms 504 KB Output is correct
4 Correct 837 ms 512 KB Output is correct
5 Correct 937 ms 504 KB Output is correct
6 Correct 804 ms 508 KB Output is correct
7 Correct 973 ms 1012 KB Output is correct
8 Correct 849 ms 504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 817 ms 1096 KB Output is correct
3 Correct 816 ms 772 KB Output is correct
4 Correct 846 ms 1200 KB Output is correct
5 Correct 867 ms 996 KB Output is correct
6 Correct 871 ms 1148 KB Output is correct
7 Correct 868 ms 956 KB Output is correct
8 Correct 869 ms 488 KB Output is correct