Submission #713871

#	Time	Username	Problem	Language	Result	Execution time	Memory
713871		victor_gao	Mechanical Doll (IOI18_doll)	C++17	53 / 100	117 ms	26972 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>to[200015],g[200015];
vector<int>ans1,ans2,c;
int n,m,now=0;
int build(int num,int l,int r,int root){
    if (l==r){
        if (g[num][l]==-1) return -root;
        else return -g[num][l];
    }
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    int p1=build(num,l,mid,root);
    ans1[use]=-p1;
    int p2=build(num,mid+1,r,root);
    ans2[use]=-p2;
    return use;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.push_back(0);
    n = A.size();
    for (int i=0;i<n-1;i++){
        to[A[i]].push_back(A[i+1]);
    }
    for (int i=1;i<=m;i++){
        if (to[i].empty()) continue;
        int p=0;
        for (int j=0; ;j++){
            if ((1LL<<j)>=(int)to[i].size()){
                p=j;
                break;
            }
        }
        g[i].resize((1LL<<p),-1);
        for (int j=0;j<to[i].size();j++){
            int idx=0;
            for (int k=0;k<p;k++){
                if (j&(1LL<<k))
                    idx=(idx+(1LL<<(p-k-1)));
            }
            if (j==to[i].size()-1)
                g[i][(1LL<<p)-1]=to[i][j];
            else g[i][idx]=to[i][j];
        }
    }
    c.resize(m+1);
    for (int i=0;i<=m;i++){
        if (g[i].empty()) c[i]=0;
        else if (g[i].size()==1) c[i]=g[i][0];
        else c[i]=-build(i,0,g[i].size()-1,now-1);
    }
    c[0]=A[0];
    now=abs(now);
    vector<int>X,Y;
    for (int i=1;i<=now;i++){
        X.push_back(ans1[i]);
    }
    for (int i=1;i<=now;i++){
        Y.push_back(ans2[i]);
    }
    answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
./rand
./doll
*/

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j=0;j<to[i].size();j++){
      |                      ~^~~~~~~~~~~~~
doll.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (j==to[i].size()-1)
      |                 ~^~~~~~~~~~~~~~~~

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