Submission #1223489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223489		iulia_morariu	Zagrade (COI20_zagrade)	C++20	100 / 100	224 ms	924 KiB

zagrade

#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <stack>
// #include <bits/stdc++.h>
#define in  cin
#define out cout

using namespace std;

string s;
vector<int> rez;

void explore(int p){
    // p si p + 1 sunt ()
    for(int i = p - 1; i > 0; i--){
        if(s[i] != '.') break;
        if(s[i + 1] == '(' && rez[i] == 0) break; // nu mai chiar pot face ceva
        if(s[i + 1] == ')' && rez[i] == 0){
            s[i] = ')'; continue;
        }
        if(s[i + 1] == ')' && rez[i] == 1){
            s[i] = '('; continue;
        }
    }

    for(int i = p + 2; i < s.size(); i++){
        if(s[i] != '.') break;
        if(s[i - 1] == ')' && rez[i] == 0) break; // nu mai chiar pot face ceva
        if(s[i - 1] == '(' && rez[i] == 0){
            s[i] = '('; continue;
        }
        if(s[i - 1] == '(' && rez[i] == 1){
            s[i] = ')'; continue;
        }
    }
}

void explore_final(int p){
    for(int i = p - 1; i > 0; i--){
        if(s[i] != '.') break;
        if(s[i + 1] == '(' && rez[i] == 0){
            s[i] = '('; continue;
        }
        if(s[i + 1] == ')' && rez[i] == 0){
            s[i] = ')'; continue;
        }
        if(s[i + 1] == ')' && rez[i] == 1){
            s[i] = '('; continue;
        }
    }
    for(int i = p + 2; i < s.size(); i++){
        if(s[i] != '.') break;
        if(s[i - 1] == ')' && rez[i] == 0){
            s[i] = ')'; continue;
        }
        if(s[i - 1] == '(' && rez[i] == 0){
            s[i] = '('; continue;
        }
        if(s[i - 1] == '(' && rez[i] == 1){
            s[i] = ')'; continue;
        }
    }
}

signed main(){

    int n, q; in >> n >> q;

    // ideea precedenta nu imi prindea cazuri de genu ))()(( -_-

    stack<int> st;

    st.push(0);
    s.resize(n);
    for(int i = 1; i < n; i++){
        if(st.empty()){
            st.push(i); continue;
        }
        cout << "? " << st.top() + 1 << " " << i + 1 << endl; // ca gen s-o inchis totul dintre ele (teoretic)
        int x; in >> x;
        if(x == 1){
            // yaay se inchid
            s[st.top()] = '(';
            s[i] = ')';
            st.pop();
        }else st.push(i);
    }

    // si e n - 1 pt ca fac cate 1 queri / i de la i la 1 la n - 1

    int sz = st.size() / 2; // ce o ramas este ))..)(..((
    while((int)st.size() > sz){
        s[st.top()] = '(';
        st.pop();
    }
    while(!st.empty()){
        s[st.top()] = ')';
        st.pop();
    }
    out << "! " << s << endl;

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 7 / 7
• Subtask 3: 57 / 57
• Subtask 4: 22 / 22