Submission #173459

#	Time	Username	Problem	Language	Result	Execution time	Memory
173459		arnold518	Mechanical Doll (IOI18_doll)	C++14	37 / 100	148 ms	12916 KiB

doll

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, M, S=0, K;
vector<int> A, C, X, Y;

void solve(int now, vector<int> &V)
{
    int i, j;
    //for(auto it : V) printf("%d ", it); printf("\n");
    if(V.size()==2)
    {
        X[now-1]=V[0];
        Y[now-1]=V[1];
        return;
    }
    vector<int> L, R;
    for(i=0; i<V.size(); i++)
    {
        if(i%2==0) L.push_back(V[i]);
        else R.push_back(V[i]);
    }
    X[now-1]=-(++S);
    Y[now-1]=-(++S);
    solve(-X[now-1], L);
    solve(-Y[now-1], R);
}

void create_circuit(int _M, vector<int> _A)
{
    int i, j;
    M=_M; A=_A; N=A.size();
    C.resize(M+1); X.resize(N*2); Y.resize(N*2);

    N++;
    while(__builtin_popcount(N)>1) N++; K=A.size();
    for(i=1; i<N-K; i++) A.push_back(-1); A.push_back(0);
    solve(++S, A);
    for(i=0; i<=M; i++) C[i]=-1;

    X.resize(S); Y.resize(S);

    //printf("C : "); for(auto it : C) printf("%d ", it); printf("\n");
    //printf("X : "); for(auto it : X) printf("%d ", it); printf("\n");
    //printf("Y : "); for(auto it : Y) printf("%d ", it); printf("\n");

    return answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void solve(int, std::vector<int>&)':
doll.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(i=0; i<V.size(); i++)
      |              ~^~~~~~~~~
doll.cpp:14:12: warning: unused variable 'j' [-Wunused-variable]
   14 |     int i, j;
      |            ^
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:41:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   41 |     while(__builtin_popcount(N)>1) N++; K=A.size();
      |     ^~~~~
doll.cpp:41:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   41 |     while(__builtin_popcount(N)>1) N++; K=A.size();
      |                                         ^
doll.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |     for(i=1; i<N-K; i++) A.push_back(-1); A.push_back(0);
      |     ^~~
doll.cpp:42:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   42 |     for(i=1; i<N-K; i++) A.push_back(-1); A.push_back(0);
      |                                           ^
doll.cpp:36:12: warning: unused variable 'j' [-Wunused-variable]
   36 |     int i, j;
      |            ^

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