oj.uz

Submission #144754

# Submission time Handle Problem Language Result Execution time Memory
144754 2019-08-17T15:55:10 Z Abelyan Zagonetka (COI18_zagonetka) C++17
100 / 100
 116 ms 19240 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=4e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

int n;
int col[N],ind[N],ans[N];
vector<int> g[N];

bool dfsc(int v,int par=-1){
    col[v]=1;
    trav(to,g[v]){
        if (col[to]==2)continue;
        if (to!=par && col[to]==1)return true;
        if (dfsc(to,v))return true;
    }
    col[v]=2;
    return false;
}

bool cikl(){
    FORT(i,0,n)col[i]=0;
    FORT(i,1,n){
        if (!col[i] && dfsc(i))return true;
    }
    return false;
}
vector<int> vc;

void dfs(int v){
    col[v]=1;
    trav(to,g[v]){
        if (!col[to])dfs(to);
    }
    vc.ad(v);
}

void topsort(int k){
    vc.clear();
    FORT(i,0,n){
        col[i]=0;
        ans[i]=0;
    }
    FORT(i,1,k){
        int v=ind[i];
        if (!col[v])dfs(v);
    }
    //int qdljbj;
    FOR(i,vc.size()){
        ans[vc[i]]=i+1;
    }
}

vector<int> hg[N];

void dfsh(int v){
    col[v]=1;
    trav(to,hg[v]){
        if (!col[to])dfsh(to);
    }
    vc.ad(v);
}

void vts(bool hak){
    vc.clear();
    FORT(i,0,n){
        col[i]=0;
        ans[i]=0;
    }
    if (!hak){
        FOR(i,n){
            if (!col[i])dfs(i);
        }
    }
    else{
        FOR(i,n){
            if (!col[i])dfsh(i);
        }
    }
    FOR(i,vc.size()){
        ans[vc[i]]=i+1;
    }
}

int tv[N];

int main(){
    fastio;
    cin>>n;
    //cout<<n<<endl;
    //assert(n<=12);
    FOR(i,n){
        cin>>tv[i];
        ind[tv[i]]=i;
    }
    //assert(tv[0]==1 && tv[1]==2 && tv[2]==3);
    //cout<<i<<endl;
    //cout<<1<<endl;
    int qanq=0;
    FORT(i,2,n){
        FORTD(j,i-1,1){
            //cout<<1<<endl;
            int a=ind[i];
            int b=ind[j];
            g[b].ad(a);
            //cout<<1<<endl;
            if (cikl()){
                g[b].pop_back();
                g[a].ad(b);
                hg[b].ad(a);
                continue;
            }
            //cout<<1<<endl;
            topsort(i);

            cout<<"query ";
            FOR(k,n){
                if (ans[k])cout<<ans[k]<<" ";
                else cout<<tv[k]<<" ";
            }
            cout<<endl;
            fflush(stdout);
            int pat;
            cin>>pat;
            //if (n==4 && qanq==5 && !pat)assert(0);
            //if (qanq==5)assert(0);
            qanq++;
            //3assert(!pat);
            g[b].pop_back();
            if (!pat){
                g[a].ad(b);
                hg[b].ad(a);
                //cout<<a<<" "<<b<<endl;
            }
            //else cout<<a<<" "<<b<<endl;
        }
    }
    assert(qanq<=5000);
    cout<<"end"<<endl;
    fflush(stdout);
    FORT(i,0,n){
        sort(all(g[i]));
        sort(all(hg[i]));
    }
    vts(false);
    bool bl=false;
    FOR(i,n){
        if (ans[i]<tv[i])bl=true;
        if (!bl && ans[i]>tv[i])assert(0);
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    vts(true);
    bl=false;
    FOR(i,n){
        if (n-ans[i]+1>tv[i])bl=true;
        if (!bl && n-ans[i]+1<tv[i])assert(0);
        cout<<n-ans[i]+1<<" ";
    }
    cout<<endl;
    fflush(stdout);
    return 0;
}

Compilation message

zagonetka.cpp: In function 'void topsort(int)':
zagonetka.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
zagonetka.cpp:72:5: note: in expansion of macro 'FOR'
     FOR(i,vc.size()){
     ^~~
zagonetka.cpp: In function 'void vts(bool)':
zagonetka.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
zagonetka.cpp:103:5: note: in expansion of macro 'FOR'
     FOR(i,vc.size()){
     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 19 ms 19064 KB Output is correct
3 Correct 20 ms 19192 KB Output is correct
4 Correct 19 ms 19064 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct
6 Correct 19 ms 19064 KB Output is correct
7 Correct 20 ms 19192 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19192 KB Output is correct
2 Correct 41 ms 19192 KB Output is correct
3 Correct 55 ms 19148 KB Output is correct
4 Correct 45 ms 19168 KB Output is correct
5 Correct 31 ms 19192 KB Output is correct
6 Correct 48 ms 19236 KB Output is correct
7 Correct 30 ms 19196 KB Output is correct
8 Correct 27 ms 19152 KB Output is correct
9 Correct 52 ms 19172 KB Output is correct
10 Correct 38 ms 19064 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19064 KB Output is correct
2 Correct 20 ms 19192 KB Output is correct
3 Correct 26 ms 19064 KB Output is correct
4 Correct 23 ms 19064 KB Output is correct
5 Correct 22 ms 19152 KB Output is correct
6 Correct 21 ms 19152 KB Output is correct
7 Correct 24 ms 19068 KB Output is correct
8 Correct 27 ms 19156 KB Output is correct
9 Correct 22 ms 19064 KB Output is correct
10 Correct 21 ms 19064 KB Output is correct
11 Correct 23 ms 19064 KB Output is correct
12 Correct 23 ms 19044 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 19192 KB Output is correct
2 Correct 82 ms 19152 KB Output is correct
3 Correct 93 ms 19192 KB Output is correct
4 Correct 27 ms 19152 KB Output is correct
5 Correct 30 ms 19156 KB Output is correct
6 Correct 32 ms 19192 KB Output is correct
7 Correct 42 ms 19192 KB Output is correct
8 Correct 47 ms 19232 KB Output is correct
9 Correct 48 ms 19192 KB Output is correct
10 Correct 116 ms 19240 KB Output is correct
11 Correct 104 ms 19064 KB Output is correct
12 Correct 89 ms 19192 KB Output is correct
13 Correct 96 ms 19064 KB Output is correct
14 Correct 84 ms 19240 KB Output is correct
15 Correct 103 ms 19192 KB Output is correct
16 Correct 77 ms 19232 KB Output is correct