Submission #713771

#	Time	Username	Problem	Language	Result	Execution time	Memory
713771		victor_gao	Mechanical Doll (IOI18_doll)	C++17	6 / 100	86 ms	20672 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>to[100015],g[100015];
vector<int>ans1,ans2,c;
int n,m,now=0;
int build(int num,int l,int r){
    if (l==r) return -g[num][l];
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    int p1=build(num,l,mid);
    ans1[use]=-p1;
    int p2=build(num,mid+1,r);
    ans2[use]=-p2;
    return use;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.insert(A.begin(),0);
    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=0;i<=m;i++){
        if (to[i].empty()) continue;
        g[i].resize(to[i].size());
        int p=0;
        for (int j=0; ;j++){
            if ((1LL<<j)>=(int)to[i].size()){
                p=j;
                break;
            }
        }
        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)));
            }
            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=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);
}

Compilation message (stderr)

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

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