Submission #330551

#	Time	Username	Problem	Language	Result	Execution time	Memory
330551		lLab_	Mechanical Doll (IOI18_doll)	C++14	10 / 100	2 ms	204 KiB

doll

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

vector<int> X,Y,C;
int cnt = 0;

int createS(int x,int y){
    cnt--;
    X.push_back(x);
    Y.push_back(y);
    return cnt;
}

int create(vector<int> v){
    bool ok = true;
    for(int i=1;i<v.size();++i){
        if(v[i] != v[i-1]){
            ok = false;
            break;
        }
    }
    if(v.size() == 1 || ok){
        return v[0];
    }

    vector<int> x,y;
    for(int i=0;i<v.size();++i){
        if(i%2==0) x.push_back(v[i]);
        else y.push_back(v[i]);
    }

    int l = create(x);
    int r = create(y);

    return createS(l,r);
}

int rev(int k,int n){
    int B = 0;
    for(int i=0;i<k;++i){
        B <<= 1;
        B = n&1;
        n >>= 1;
    }
    return B;
}

void create_circuit(int M,vector<int> A) {
    int N = A.size();
    int nn = 0;

    while(1<<nn < N){
        nn++;
    }
    int k = nn-1;
    nn = 1<<nn;

    vector<int> v(nn,0);

    for(int i=0;i<nn-N;++i){
        v[rev(k,i)] = 2e9;
    }

    int curr = 0;
    for(int i=1;i<A.size();++i){
        while(v[curr] == 2e9) curr++;
        v[curr] = A[i];
        curr++;
    }

    v[nn-1] = 0;

    int root = create(v);

    for(int i=0;i<X.size();++i){
        if(X[i] == 2e9) X[i] = root;
    }
    for(int i=0;i<Y.size();++i){
        if(Y[i] == 2e9) Y[i] = root;
    }

    C.resize(M+1,root);
    C[0] = A[0];

    return answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'int create(std::vector<int>)':
doll.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<v.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v.size();++i){
      |                 ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=1;i<A.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<X.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<Y.size();++i){
      |                 ~^~~~~~~~~

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