oj.uz

답안 #236609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236609 2020-06-02T14:50:07 Z LittleFlowers__ 도서관 (JOI18_library) C++17
0 / 100
 262 ms 632 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);

#include "library.h"

int n;
int mode;

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,int has=2){
    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,1);
        if(has>1) dnc1(r,i,1);
    } else if(l.size()==to){
        dnc1(r,i,has);
    } else{
        l.pop_back();
        dnc1(l,i,has);
    }
}

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){
            pf=sf=0;
            if(i==4) mode=1;
            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;
            }
        }
        tot=tmp;
    }
    forinc(i,1,n){
        if(ad[i].size()==1){
            vector<int> ans(n);
          	ans[0]=i;
            int pre=-1;
            forinc(j,2,n){
                forv(t,ad[i]){
                    if(t!=pre){
                      	ans[j-1]=i;
                        pre=i;
                        i=t;
                        break;
                    }
                }
            }
            vector<int> dup(n+1);

            forv(i,ans){
                if(++dup[i]>1)
                    exit(-1);
            }
            Answer(ans);
            gg
        }
    }
    exit(-1);
}

Compilation message

library.cpp: In function 'int dnc(std::vector<int>, int)':
library.cpp:57: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, int)':
library.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l.size()==to+1){
        ~~~~~~~~^~~~~~
library.cpp:77: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 23 ms 384 KB Execution failed because the return code was nonzero
2 Runtime error 22 ms 384 KB Execution failed because the return code was nonzero
3 Runtime error 23 ms 384 KB Execution failed because the return code was nonzero
4 Runtime error 26 ms 384 KB Execution failed because the return code was nonzero
5 Runtime error 21 ms 420 KB Execution failed because the return code was nonzero
6 Runtime error 25 ms 384 KB Execution failed because the return code was nonzero
7 Runtime error 26 ms 384 KB Execution failed because the return code was nonzero
8 Runtime error 29 ms 512 KB Execution failed because the return code was nonzero
9 Runtime error 31 ms 384 KB Execution failed because the return code was nonzero
10 Runtime error 12 ms 456 KB Execution failed because the return code was nonzero
11 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
12 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
13 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
14 Runtime error 5 ms 384 KB Execution failed because the return code was nonzero
15 Runtime error 5 ms 384 KB Execution failed because the return code was nonzero
16 Runtime error 6 ms 384 KB Execution failed because the return code was nonzero

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 384 KB Execution failed because the return code was nonzero
2 Runtime error 22 ms 384 KB Execution failed because the return code was nonzero
3 Runtime error 23 ms 384 KB Execution failed because the return code was nonzero
4 Runtime error 26 ms 384 KB Execution failed because the return code was nonzero
5 Runtime error 21 ms 420 KB Execution failed because the return code was nonzero
6 Runtime error 25 ms 384 KB Execution failed because the return code was nonzero
7 Runtime error 26 ms 384 KB Execution failed because the return code was nonzero
8 Runtime error 29 ms 512 KB Execution failed because the return code was nonzero
9 Runtime error 31 ms 384 KB Execution failed because the return code was nonzero
10 Runtime error 12 ms 456 KB Execution failed because the return code was nonzero
11 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
12 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
13 Runtime error 4 ms 384 KB Execution failed because the return code was nonzero
14 Runtime error 5 ms 384 KB Execution failed because the return code was nonzero
15 Runtime error 5 ms 384 KB Execution failed because the return code was nonzero
16 Runtime error 6 ms 384 KB Execution failed because the return code was nonzero
17 Runtime error 253 ms 504 KB Execution failed because the return code was nonzero
18 Runtime error 239 ms 384 KB Execution failed because the return code was nonzero
19 Runtime error 230 ms 504 KB Execution failed because the return code was nonzero
20 Runtime error 253 ms 632 KB Execution failed because the return code was nonzero
21 Runtime error 210 ms 484 KB Execution failed because the return code was nonzero
22 Runtime error 249 ms 424 KB Execution failed because the return code was nonzero
23 Runtime error 262 ms 384 KB Execution failed because the return code was nonzero
24 Runtime error 94 ms 384 KB Execution failed because the return code was nonzero
25 Runtime error 260 ms 560 KB Execution failed because the return code was nonzero
26 Runtime error 221 ms 548 KB Execution failed because the return code was nonzero
27 Runtime error 89 ms 384 KB Execution failed because the return code was nonzero
28 Runtime error 56 ms 384 KB Execution failed because the return code was nonzero
29 Runtime error 52 ms 384 KB Execution failed because the return code was nonzero
30 Runtime error 57 ms 444 KB Execution failed because the return code was nonzero