Submission #971969

#	Time	Username	Problem	Language	Result	Execution time	Memory
971969		onlk97	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	86 ms	15116 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100010],C,X,Y;
vector <int> seq;
void gen(int len){
    seq={1};
    int add=1;
    while (seq.size()<len){
        vector <int> c;
        for (int i=0; i<seq.size(); i++){
            c.push_back(seq[i]);
            c.push_back(seq[i]+add);
        }
        seq=c;
        add*=2;
    }
}
int rt,ptr;
vector <int> use;
int build(int rem,int po){
    if (po==1){
        use.push_back(seq[ptr]);
        ptr++;
        return -1e9;
    }
    int cur=-(1+X.size());
    X.push_back(-1e9); Y.push_back(-1e9);
    int br=X.size()-1;
    if (rem<=po/2){
        int tf=build(rem,po/2);
        X[br]=tf;
        Y[br]=rt;
        ptr+=po/2;
    } else {
        int tf=build(rem-po/2,po/2);
        X[br]=tf;
        int tg=build(po/2,po/2);
        Y[br]=tg;
    }
    return cur;
}
void create_circuit(int M,vector <int> A){
    v[0].push_back(A[0]);
    for (int i=1; i<A.size(); i++) v[A[i-1]].push_back(A[i]);
    v[A.back()].push_back(0);
    for (int i=0; i<=M; i++) C.push_back(0);
    for (int i=0; i<=M; i++){
        if (v[i].empty()) continue;
        if (v[i].size()==1){
            C[i]=v[i][0];
            continue;
        }
        int sz=v[i].size(),rd=1;
        while (rd<sz) rd*=2;
        gen(rd);
        rt=-(1+X.size());
        C[i]=rt;
        int ori=X.size();
        use.clear(); ptr=0;
        build(sz,rd);
        vector <pair <int,int> > vv;
        for (int j=ori; j<X.size(); j++){
            if (X[j]==-1e9) vv.push_back({j,0});
            if (Y[j]==-1e9) vv.push_back({j,1});
        }
        vector <int> suse;
        for (int j:use) suse.push_back(j);
        sort(suse.begin(),suse.end());
        for (int j=0; j<use.size(); j++) use[j]=lower_bound(suse.begin(),suse.end(),use[j])-suse.begin();
        //assert(vv.size()==use.size());
        for (int j=0; j<vv.size(); j++){
            if (!vv[j].second) X[vv[j].first]=v[i][use[j]];
            else Y[vv[j].first]=v[i][use[j]];
        }
    }
    answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void gen(int)':
doll.cpp:9:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |     while (seq.size()<len){
      |            ~~~~~~~~~~^~~~
doll.cpp:11:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int i=0; i<seq.size(); i++){
      |                       ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=1; i<A.size(); i++) v[A[i-1]].push_back(A[i]);
      |                   ~^~~~~~~~~
doll.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int j=ori; j<X.size(); j++){
      |                         ~^~~~~~~~~
doll.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int j=0; j<use.size(); j++) use[j]=lower_bound(suse.begin(),suse.end(),use[j])-suse.begin();
      |                       ~^~~~~~~~~~~
doll.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j=0; j<vv.size(); j++){
      |                       ~^~~~~~~~~~

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