Submission #1131863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131863		StefanSebez	Mechanical Doll (IOI18_doll)	C++20	16 / 100	441 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>X,Y;
vector<int>susedni[N];
int pws[30],LOG[N+50];
int S;
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;
        vector<int>bits;
        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();
    vector<int>C(m+1,0);
    C[0]=A[0];
    X.pb(0),Y.pb(0);
    X.resize(3*N),Y.resize(3*N);
    for(int i=0;i<n;i++) susedni[A[i]].pb(A[i+1]);
    for(int i=1;i<=m;i++){
        vector<int>temp=susedni[i];
        if(temp.size()==1) C[i]=susedni[i][0];
        if(temp.size()<=1) continue;
        int k=temp.size();for(int j=0;j<=29;j++) if(pws[j]>=k){k=pws[j];break;}
        reverse(temp.begin(),temp.end());
        while(temp.size()<k) temp.pb(-S-1);
        reverse(temp.begin(),temp.end());
        //printf("%i: ",i);for(auto j:temp) printf("%i ",j);printf("\n");
        Resi(C[i],0,temp.size()-1,temp);
    }
    //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