oj.uz

답안 #236555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236555 2020-06-02T13:18:06 Z LittleFlowers__ 도서관 (JOI18_library) C++17
0 / 100
 55 ms 888 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

//#define unx 1

#ifndef unx
#include "library.h"
#endif // unx

#ifdef unx
int n;
int a[1111];
void Answer(const vector<int>&q){
    forv(i,q) cout<<i<<" ";
    gg
}
int Query(const vector<int>&q){
    int has=0, tot=0;
    forinc(i,1,n){
        if(q[a[i]-1]){
            tot+=!has;
            has=1;
        } else has=0;
    }
    return tot;
}
#endif // unx

int n;
int x[1111], y[1111], id[1111];

int root(int i){
    return !id[i] ? i : id[i]=root(id[i]);
}
void join(int i,int j){
    if((i=root(i))==(j=root(j))) return;
    id[i]=j;
}

int tim(const vector<int>&q,int mode=1){
    vector<int> fac(n), ask(n);
    if(mode){
        forv(i,q) fac[i-1]=1;
        forinc(i,1,n) if(fac[root(i)-1]) ask[i-1]=1;
    } else{
        forv(i,q) ask[i-1]=1;
    }
    return Query(ask);
}

int dnc(vector<int> l,int i){
    if(l.back()==i) l.pop_back();
    if(l.size()<2) return l[0];
    vector<int> r;
    while(l.size()>r.size()){
        r.push_back(l.back());
        l.pop_back();
    }
    l.push_back(i);
    return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
}

int pf,sf;
void dnc1(vector<int> l,int i){
    if(l.size()<2){
        if(pf) sf=l[0]; else pf=l[0];
        return;
    }

    vector<int> r;
    while(l.size()>r.size()){
        r.push_back(l.back());
        l.pop_back();
    }
    l.push_back(i);
    int to=tim(l);
    if(l.size()==to+1){
        l.pop_back();
        dnc1(l,i);
        dnc1(r,i);
    } else if(l.size()==to){
        dnc1(r,i);
    } else{
        l.pop_back();
        dnc1(l,i);
    }

}

vector<int> ad[1111];

void add(int i,int j){
    ad[i].push_back(j);
    ad[j].push_back(i);
}

void Solve(int N){
    n=N;
    vector<int> ask(n);
    ask[0]=x[1]=y[1]=1;

    vector<int> mp={1};

    int tot=1;
    forinc(i,2,n){
        ask[i-1]=1;
        int tmp=Query(ask);
        if(tot<tmp){
            mp.push_back(i);
            x[i]=y[i]=i;
        } else if(tot>tmp){
            //cerr<<i<<"\n";
            pf=sf=0;
            dnc1(mp,i);

            join(pf,i);
            join(sf,i);

            if(tim({x[pf],i},0)==1) add(x[pf],i), x[i]=y[pf]; else add(y[pf],i), y[i]=x[pf];
            if(tim({x[sf],i},0)==1) add(x[sf],i), (x[i] ? y[i]=y[sf] : x[i]=y[sf]); else add(y[sf],i), (x[i] ? y[i]=x[sf] : x[i]=x[sf]);
            fordec(i,mp.size()-1,0){
                if(mp[i]==pf || mp[i]==sf){
                    swap(mp[i],mp.back());
                    mp.pop_back();
                }
            }
            mp.push_back(i);
        } else{
            int to=dnc(mp,i);


            join(i,to);
            if(tim({x[to],i},0)==1){
                add(i,x[to]);
                x[to]=i;
            } else{
                add(i,y[to]);
                y[to]=i;
            }
        }
        //forv(j,mp) cerr<<j<<" "; cerr<<":"<<tmp<<"\n";
        //cout<<"\n";
        tot=tmp;
    }
    //forv(i,ad[10]) cerr<<i<<" ";
    //gg
    forinc(i,1,n){
        if(ad[i].size()==1){
            vector<int> ans={i};
            int pre=-1;
            forinc(j,2,n){
                forv(t,ad[i]){
                    if(t!=pre){
                        ans.push_back(t);
                        pre=i;
                        i=t;
                        break;
                    }
                }
            }
            Answer(ans);
            gg
        }
    }

}

#ifdef unx
main(){
    #define task "vim"
    freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    forinc(i,1,n=in) a[i]=in;
    Solve(n);
}
#endif // unx

Compilation message

library.cpp: In function 'int dnc(std::vector<int>, int)':
library.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
            ~~~~~~~^~~~~~~~~~
library.cpp: In function 'void dnc1(std::vector<int>, int)':
library.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l.size()==to+1){
        ~~~~~~~~^~~~~~
library.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     } else if(l.size()==to){
               ~~~~~~~~^~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 11 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 4 ms 384 KB Wrong Answer [7]
12 Incorrect 4 ms 384 KB Unexpected end of file - token expected
13 Incorrect 5 ms 384 KB Unexpected end of file - token expected
14 Incorrect 5 ms 384 KB Unexpected end of file - token expected
15 Incorrect 5 ms 384 KB Unexpected end of file - token expected
16 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 11 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 4 ms 384 KB Wrong Answer [7]
12 Incorrect 4 ms 384 KB Unexpected end of file - token expected
13 Incorrect 5 ms 384 KB Unexpected end of file - token expected
14 Incorrect 5 ms 384 KB Unexpected end of file - token expected
15 Incorrect 5 ms 384 KB Unexpected end of file - token expected
16 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 26 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 16 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 31 ms 812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 40 ms 736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 17 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 17 ms 848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 29 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 16 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 34 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 20 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 25 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 55 ms 384 KB Unexpected end of file - token expected
29 Incorrect 52 ms 384 KB Unexpected end of file - token expected
30 Incorrect 54 ms 504 KB Unexpected end of file - token expected