Submission #119638

#	Time	Username	Problem	Language	Result	Execution time	Memory
119638		alexandra_udristoiu	Mechanical Doll (IOI18_doll)	C++14	100 / 100	198 ms	13292 KiB

doll

#include<iostream>
#include<vector>
#define DIM 200005
#include "doll.h"
using namespace std;
static int nr, k;
static vector<int> xsol, ysol, c;
static int w[DIM], st[DIM], v[DIM][2], pt[20];
static void solve(int nod, int niv, int n){
    if(n == 0 || niv == 1){
        return;
    }
    if(n <= pt[niv - 1]){
        v[nod][1] = ++k;
        solve(v[nod][1], niv - 1, n);
    }
    else{
        v[nod][1] = ++k;
        solve(v[nod][1], niv - 1, pt[niv - 1]);
        v[nod][0] = ++k;
        solve(v[nod][0], niv - 1, n - pt[niv - 1]);
    }
}
static void drum(int nod, int niv){
    if(nod == 0){
        return;
    }
    if(niv == 1){
        w[++nr] = nod;
        return;
    }
    drum(v[nod][ st[nod] ], niv - 1);
    st[nod] = 1 - st[nod];
}
void create_circuit(int m, vector<int> a){
    int n, i, j, p;
    n = a.size();
    a.push_back(0);
    pt[0] = 1;
    for(i = 1; ; i++){
        pt[i] = 2 * pt[i - 1];
        if(pt[i] >= n){
            p = i;
            break;
        }
    }
    k = 1;
    solve(1, p, n);
    nr = 0;
    for(i = 1; i <= pt[p]; i++){
        drum(1, p);
    }
    for(i = 1; i <= k; i++){
        v[i][0] = -v[i][0];
        v[i][1] = -v[i][1];
    }
    if(nr == n){
        for(i = 1; i <= n; i++){
            if(v[ w[i] ][0] == 0){
                v[ w[i] ][0] = a[i];
            }
            else{
                v[ w[i] ][1] = a[i];
            }
        }
    }
    else{
        v[ w[1] ][0] = -1;
        for(i = 2; i <= nr; i++){
            if(v[ w[i] ][0] == 0){
                v[ w[i] ][0] = a[i - 1];
            }
            else{
                v[ w[i] ][1] = a[i - 1];
            }
        }
    }
    for(i = 1; i <= k; i++){
        if(v[i][0] == 0){
            v[i][0] = -1;
        }
        if(v[i][1] == 0){
            v[i][1] = -1;
        }
    }
    v[ w[nr] ][1] = 0;
    for(i = 1; i <= k; i++){
        xsol.push_back(v[i][0]);
        ysol.push_back(v[i][1]);
    }
    c.push_back(a[0]);
    for(i = 1; i <= m; i++){
        c.push_back(-1);
    }
    answer(c, xsol, ysol);
    return;
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:15: warning: unused variable 'j' [-Wunused-variable]
   36 |     int n, i, j, p;
      |               ^

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