Submission #381454

#TimeUsernameProblemLanguageResultExecution timeMemory
381454VEGAnnZagrade (COI20_zagrade)C++14
21 / 100
1139 ms748 KiB
#include <bits/stdc++.h> #define i2 array<int,2> #define sz(x) ((int)x.size()) using namespace std; set<i2> st; string s; int n, q; int query(int a, int b){ cout << "? " << a + 1 << " " << b + 1 << endl; int res; cin >> res; return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL // freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n >> q; s = ""; for (int i = 0; i < n; i++) s += "?"; for (int i = 1; i < n; ){ int res = query(i - 1, i); if (!res){ i++; } else { int l = i - 1, r = i; s[l] = '('; s[r] = ')'; while (1){ while (sz(st) > 0){ i2 cr = (*(--st.end())); if (cr[1] + 1 != l) break; l = cr[0]; st.erase(cr); } if (l == 0 || r == n - 1) break; res = query(l - 1, r + 1); if (!res) break; s[l - 1] = '('; s[r + 1] = ')'; l--; r++; } i = r + 1; st.insert({l, r}); } } int cnt = 0; for (int i = 0; i < sz(s); i++) cnt += bool(s[i] == '?'); assert(cnt % 2 == 0); cnt /= 2; for (int i = 0; i < sz(s); i++) if (s[i] == '?'){ s[i] = (cnt > 0 ? ')' : '('); cnt--; } cout << "! " << s << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...