oj.uz

Submission #447965

# Submission time Handle Problem Language Result Execution time Memory
447965 2021-07-28T09:55:39 Z MOUF_MAHMALAT Zagrade (COI20_zagrade) C++11
100 / 100
 1085 ms 1404 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,q,a[100009],x,p[100009],id=2,o;
bool b;
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    x=n>>1;
    for(ll i=1; i<=n; i++)
        p[i]=i;
    while(id<=n)
    {
        o=gp(id-1);
        if(o==0)
        {
            id++;
            continue;
        }
        cout<<"? "<<o<<" "<<id<<endl;
        cin>>b;
        if(b)
        {
            x--;
            a[id]=-1;
            a[o]=1;
            p[id]=p[o]=o-1;
        }
        id++;
    }
    cout<<"! ";
    for(ll i=1; i<=n; i++)
    {
        if(a[i]==1)
            cout<<"(";
        else if(a[i]==-1)
            cout<<")";
        else if(x)
        {
            x--;
            cout<<")";
        }
        else
            cout<<"(";
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 7 ms 200 KB Output is correct
3 Correct 11 ms 200 KB Output is correct
4 Correct 12 ms 328 KB Output is correct
5 Correct 9 ms 324 KB Output is correct
6 Correct 9 ms 324 KB Output is correct
7 Correct 10 ms 324 KB Output is correct
8 Correct 13 ms 200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 9 ms 200 KB Output is correct
3 Correct 9 ms 328 KB Output is correct
4 Correct 12 ms 200 KB Output is correct
5 Correct 12 ms 324 KB Output is correct
6 Correct 15 ms 200 KB Output is correct
7 Correct 14 ms 328 KB Output is correct
8 Correct 13 ms 200 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 518 ms 1240 KB Output is correct
3 Correct 969 ms 1212 KB Output is correct
4 Correct 911 ms 1144 KB Output is correct
5 Correct 817 ms 1176 KB Output is correct
6 Correct 1045 ms 1252 KB Output is correct
7 Correct 969 ms 1080 KB Output is correct
8 Correct 1085 ms 1080 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 993 ms 688 KB Output is correct
3 Correct 768 ms 1140 KB Output is correct
4 Correct 954 ms 1220 KB Output is correct
5 Correct 912 ms 1244 KB Output is correct
6 Correct 911 ms 1404 KB Output is correct
7 Correct 1018 ms 1156 KB Output is correct
8 Correct 847 ms 1124 KB Output is correct