제출 #1131864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131864		StefanSebez	자동 인형 (IOI18_doll)	C++20	16 / 100	434 ms	327680 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50;
vector<int>C,X,Y;
vector<int>susedni[N];
int pws[30],LOG[N+50];
int S;vector<int>bits;
void Resi(int &c,int ss,int se,vector<int>&a){
    c=-(++S);
    int ind=S;
    if(ss+1==se){
        int n=a.size();
        int k=ss>>1,L=LOG[n]-1;
        bits.clear();
        while(L--) bits.pb(k&1),k>>=1;
        k=0;for(int i=bits.size()-1,e=1;i>=0;i--,e<<=1) if(bits[i]) k+=e;
        X[ind]=a[k];
        Y[ind]=a[k+n/2];
        //printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
        return;
    }
    int mid=ss+se>>1;
    Resi(X[ind],ss,mid,a);
    Resi(Y[ind],mid+1,se,a);
    //printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
}
void create_circuit(int m,vector<int> A) {
    for(int i=0,e=1;i<=29;i++,e<<=1)pws[i]=e;
    for(int i=1,e=1,ct=-1;i<=N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
    A.pb(0);int n=A.size();
    for(int i=0;i<m+1;i++) C.pb(0);
    C[0]=A[0];
    X.pb(0),Y.pb(0);
    X.resize(5*N),Y.resize(5*N);
    for(int i=0;i<n;i++) susedni[A[i]].pb(A[i+1]);
    for(int i=1;i<=m;i++){
        int k=susedni[i].size();
        if(k==1) C[i]=susedni[i][0];
        if(k<=1) continue;
        for(int j=0;j<=29;j++) if(pws[j]>=k){k=pws[j];break;}
        reverse(susedni[i].begin(),susedni[i].end());
        while(susedni[i].size()<k) susedni[i].pb(-S-1);
        reverse(susedni[i].begin(),susedni[i].end());
        //printf("%i: ",i);for(auto j:temp) printf("%i ",j);printf("\n");
        Resi(C[i],0,susedni[i].size()-1,susedni[i]);
    }
    //for(auto &i:X) i=-i;
    //for(auto &i:Y) i=-i;
    while(X.size()>S+1) X.pop_back();
    while(Y.size()>S+1) Y.pop_back();
    reverse(X.begin(),X.end());X.pop_back();reverse(X.begin(),X.end());
    reverse(Y.begin(),Y.end());Y.pop_back();reverse(Y.begin(),Y.end());
    answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56