Submission #1223488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223488		iulia_morariu	Zagrade (COI20_zagrade)	C++20	0 / 100	227 ms	864 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++){
        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 << '\n';

    // rez.resize(n);
    // s.resize(n + 1);
    // bool are1 = 0;
    // for(int i = 1; i + 1 <= n; i++){
    //     s[i] = s[i + 1] = '.';
    //     cout << "? " << i << " " << i + 1 << endl;
    //     in >> rez[i];
    //     if(rez[i] == 1) are1 = 1;
    // }

    // for(int i = 1; i + 1 <= n; i++){
    //     if(rez[i] == 1){
    //         s[i] = '('; s[i + 1] = ')';
    //         explore(i);
    //     }
    // }

    // for(int i = 1; i <= n; i++){
    //     if(s[i] == '.') continue;
    //     explore_final(i);
    // }
    // s.erase(s.begin());

    // if(!are1){
    //     for(int i = 0; i < s.size() / 2; i++) s[i] = ')';
    //     for(int i = s.size() / 2; i < s.size(); i++) s[i] = '(';
    // }

    // cout << "! " << s << endl;

    return 0;
}

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