Submission #296056

#	Time	Username	Problem	Language	Result	Execution time	Memory
296056		Autoratch	Mechanical Doll (IOI18_doll)	C++14	15 / 100	119 ms	22832 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 1;

int sw;
vector<int> nxt[N];
int x[N],y[N];
vector<int> ls;
int idd = 1;

void build(int l,int r,int idx)
{
    x[idx] = -idx*2,y[idx] = -(idx*2+1);
    idd = max(idd,idx+1);
    if(l+1==r) return void(ls.push_back(idx));
    int m = (l+r)/2;
    build(l,m,idx*2),build(m+1,r,idx*2+1);
}

void create_circuit(int m,vector<int> a) 
{
    int n = a.size();
    vector<int> c(m+1);
    a.push_back(0);
    for(int i = 0;i < n;i++) nxt[a[i]].push_back(a[i+1]);
    c[0] = a[0];
    for(int i = 1;i <= m;i++) if(!nxt[i].empty())
    {
        if(nxt[i].size()==1){ c[i] = nxt[i][0]; continue; }
        int depth = 0;
        for(int j = 0;;j++) if((1 << j)>=nxt[i].size()){ depth = j; break; }
        ls.clear();
        int stt = idd;
        build(0,(1 << depth)-1,idd);
        assert(idd<=1e6);
        c[i] = -stt;
        for(int j = 0;j < ls.size();j++)
        {
            int id = j*2,ie = j*2+1,ix = 0,iy = 0;
            for(int k = 0;k < depth;k++) if(id&(1 << k)) ix+=(1 << (depth-1-k));
            for(int k = 0;k < depth;k++) if(ie&(1 << k)) iy+=(1 << (depth-1-k));
            if(ix<(1 << depth)-nxt[i].size()) x[ls[j]] = -stt;
            else x[ls[j]] = nxt[i][ix-((1 << depth)-nxt[i].size())];
            if(iy<(1 << depth)-nxt[i].size()) y[ls[j]] = -stt;
            else y[ls[j]] = nxt[i][iy-((1 << depth)-nxt[i].size())];
        }
    }
    sw = idd-1;
    vector<int> sx,sy;
    for(int i = 1;i <= sw;i++) sx.push_back(x[i]),sy.push_back(y[i]);
    answer(c,sx,sy);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:33:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j = 0;;j++) if((1 << j)>=nxt[i].size()){ depth = j; break; }
      |                                ~~~~~~~~^~~~~~~~~~~~~~~
doll.cpp:39:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0;j < ls.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(ix<(1 << depth)-nxt[i].size()) x[ls[j]] = -stt;
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             if(iy<(1 << depth)-nxt[i].size()) y[ls[j]] = -stt;
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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