oj.uz

Submission #144603

# Submission time Handle Problem Language Result Execution time Memory
144603 2019-08-17T09:30:47 Z Abelyan Zagonetka (COI18_zagonetka) C++17
18 / 100
 103 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<=3);
    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;

    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();
                continue;
            }
            //cout<<1<<endl;
            topsort(i);

            cout<<"query ";
            FOR(k,n){
                if (ans[k])cout<<ans[k]<<" ";
                else cout<<tv[k]<<" ";
            }
            cout<<endl;
            int pat;
            cin>>pat;
            //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;
        }
    }
    cout<<"end"<<endl;
    vts(false);
    FOR(i,n)cout<<ans[i]<<" ";
    cout<<endl;
    vts(true);
    FOR(i,n)cout<<n-ans[i]+1<<" ";
    cout<<endl;
    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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19192 KB Output is correct
2 Incorrect 19 ms 19064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19060 KB Output is correct
2 Correct 48 ms 19192 KB Output is correct
3 Correct 41 ms 19148 KB Output is correct
4 Correct 57 ms 19064 KB Output is correct
5 Correct 30 ms 19064 KB Output is correct
6 Correct 58 ms 19192 KB Output is correct
7 Correct 22 ms 19064 KB Output is correct
8 Correct 28 ms 19064 KB Output is correct
9 Correct 55 ms 19064 KB Output is correct
10 Correct 36 ms 19152 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19064 KB Output is correct
2 Incorrect 20 ms 19240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 19148 KB Output is correct
2 Correct 100 ms 19148 KB Output is correct
3 Correct 92 ms 19192 KB Output is correct
4 Correct 23 ms 19148 KB Output is correct
5 Correct 25 ms 19064 KB Output is correct
6 Correct 24 ms 19064 KB Output is correct
7 Incorrect 38 ms 19236 KB Output isn't correct
8 Halted 0 ms 0 KB -