Submission #320971

#	Time	Username	Problem	Language	Result	Execution time	Memory
320971		arnold518	Mechanical Doll (IOI18_doll)	C++14	100 / 100	156 ms	14916 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;

const int MAXN = 4e5;

vector<int> V;
int N, M, A[MAXN+10];
int B[MAXN+10], X[MAXN+10], Y[MAXN+10], C[MAXN+10], ncnt;

int solve(int l, int r)
{
    bool flag=true;
    for(int i=l; i<=r; i++) if(B[i]!=-1) flag=false;
    if(flag) return -1;
    if(l==r) return B[l];
    int mid=l+r>>1;

    int node=++ncnt;
    X[node]=solve(l, mid);
    Y[node]=solve(mid+1, r);
    return -node;
}

void create_circuit(int _M, vector<int> _A)
{
    M=_M; N=_A.size();
    for(int i=0; i<N; i++) A[i]=_A[i];
    A[N]=0; N++;

    V.push_back(1);
    V.push_back(2);
    while(V.size()<N)
    {
        vector<int> VV;
        for(auto it : V) VV.push_back(it*2-1);
        for(auto it : V) VV.push_back(it*2);
        V=VV;
    }

    vector<pii> V2;
    for(int i=V.size()-N; i<V.size(); i++) V2.push_back({V[i], i});
    sort(V2.begin(), V2.end());
    for(int i=0; i<V2.size(); i++) B[V2[i].second]=A[i];
    for(int i=0; i<V.size()-N; i++) B[i]=-1;

    //for(int i=0; i<V.size(); i++) printf("%d ", B[i]); printf("\n");

    solve(0, V.size()-1);
    C[0]=-1;
    for(int i=1; i<=M; i++) C[i]=-1;

    vector<int> CC, XX, YY;
    for(int i=0; i<=M; i++) CC.push_back(C[i]);
    for(int i=1; i<=ncnt; i++) XX.push_back(X[i]);
    for(int i=1; i<=ncnt; i++) YY.push_back(Y[i]);

    //for(int i=1; i<=ncnt; i++) printf("%d : %d %d\n", i, X[i], Y[i]);

    answer(CC, XX, YY);
}

Compilation message (stderr)

doll.cpp: In function 'int solve(int, int)':
doll.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid=l+r>>1;
      |             ~^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     while(V.size()<N)
      |           ~~~~~~~~^~
doll.cpp:46:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=V.size()-N; i<V.size(); i++) V2.push_back({V[i], i});
      |                           ~^~~~~~~~~
doll.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0; i<V2.size(); i++) B[V2[i].second]=A[i];
      |                  ~^~~~~~~~~~
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0; i<V.size()-N; i++) B[i]=-1;
      |                  ~^~~~~~~~~~~

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