oj.uz

Submission #276298

# Submission time Handle Problem Language Result Execution time Memory
276298 2020-08-20T11:57:15 Z PKhing Zagonetka (COI18_zagonetka) C++14
100 / 100
 1336 ms 424 KB 
#include<bits/stdc++.h>
#define FOR(i,a) for(int i=0;i<a;i++)
#define FOR1(i,a) for(int i=1;i<=a;i++)
#define db(a) printf("<%d> ",a)
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb emplace_back
#define p emplace
#define ii pair<int,int>
#define ll long long
#define rf() freopen("_working/input.in","r",stdin)
#define pf() freopen("_working/output.out","w+",stdout)
using namespace std;
const int INF=1e9;
int tab[105];
int x[105];
int visit[105];
int edge[105][105];
vector<int> e[105];
int deg[105];
int n;
int q=0;
int query(){
    FOR1(i,n){
        x[tab[i]]=i;
    }
    printf("query ");
    for(int i=1;i<=n;i++){
        printf("%d ",x[i]);
    }
    cout<<endl;
    int x;
    cin>>x;
    q++;
    return !x;
}
void find(int i){
    visit[tab[i]]=1;
    while(i>1&&edge[tab[i-1]][tab[i]]!=1){
        swap(tab[i],tab[i-1]);
         if(edge[tab[i-1]][tab[i]]==-1){
             i--;
             continue;
         }
        if(query()){
            swap(tab[i],tab[i-1]);
            edge[tab[i-1]][tab[i]]=1;
            find(i-1);
            continue;
        }
        else{
            edge[tab[i-1]][tab[i]]=-1;
            i--;
        }
    }
}
int t=1;
int cnt = 1;
int getmnn(int u){
    int mn = u;
    for(auto v:e[u]){
        if(!visit[v])mn = min(mn,getmnn(v));
    }
    return mn;
}
int getmn(int u){
    int mn = INF;
    for(auto v:e[u]){
        if(!visit[v])mn = min(mn,getmnn(v));
    }
    return mn;
}
void go(int i){
    int x = getmn(i);
    while(x!=INF){
        go(x);
        x= getmn(i);
    }
    visit[i]=1;
    if(t==1)tab[i]=cnt++;
    else tab[i]=cnt--;
}
int main(){
    cin>>n;  
    FOR1(i,n){
        cin>>x[i];
        tab[x[i]]=i;
    }   
    FOR1(i,n){
        for(int j=i-1;j>0;j--)edge[tab[j]][tab[i]]=-1;
        edge[i][i]=-1;
    }
    
    // FOR1(i,n){
    //     FOR1(j,n){printf("%2d ",edge[i][j]);}
    //     cout<<endl;
 
    // }
 
    while(visit[tab[n]]!=1){
        find(n);
    }
    printf("end");
    cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(edge[j][i]==1){
                e[i].pb(j);
            }
        }
    }
    FOR1(i,n)visit[i]=0;
    FOR1(i,n)if(!visit[i])go(i);
    FOR1(i,n)printf("%d ",tab[i]);
    FOR1(i,n)e[i].clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(edge[j][i]==1){
                e[j].pb(i);
            }
        }
    }
    cout<<endl;
    t=0;
    cnt = n;
    FOR1(i,n)visit[i]=0;
    FOR1(i,n)if(!visit[i])go(i);
    FOR1(i,n)printf("%d ",tab[i]);
    cout<<endl;
    // cout<<q<<endl;
    // FOR1(i,n){
    //     FOR1(j,n){printf("%2d ",edge[i][j]);}
    //     cout<<endl;
 
    // }
}

Subtask #1
9.0 / 9.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 35 ms 384 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 38 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 41 ms 384 KB Output is correct
10 Correct 21 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 384 KB Output is correct
2 Correct 102 ms 384 KB Output is correct
3 Correct 84 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 424 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1336 ms 408 KB Output is correct
8 Correct 32 ms 384 KB Output is correct
9 Correct 28 ms 412 KB Output is correct
10 Correct 99 ms 384 KB Output is correct
11 Correct 81 ms 384 KB Output is correct
12 Correct 84 ms 384 KB Output is correct
13 Correct 86 ms 384 KB Output is correct
14 Correct 85 ms 384 KB Output is correct
15 Correct 97 ms 384 KB Output is correct
16 Correct 82 ms 384 KB Output is correct