Submission #284725

#	Time	Username	Problem	Language	Result	Execution time	Memory
284725		peti1234	Mechanical Doll (IOI18_doll)	C++17	12 / 100	73 ms	10224 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int c=260002;
int n, po=1, db, sw, el[c], pos, cnt;
vector<int> s, x, y, sz;
bool v[c], akt[c];
void dfs(int a, int x) {
    if (a>=po) return;
    if (db-n>=x) {db-=x, sw-=x-1, v[a]=1; return;}
    dfs(2*a, x/2), dfs(2*a+1, x/2);
}
void dfs2(int a) {
    if (a>=po) return;
    if (v[a]) {el[a]=1; return;}
    cnt++, el[a]=cnt;
    if (a<po/2) {
        dfs2(2*a), x[el[a]-1]=-el[2*a];
        dfs2(2*a+1), y[el[a]-1]=-el[2*a+1];
    }
}
void dfs3(int a) {
    if (v[a]) return;
    if (a<po/2) {
        dfs3(2*a+akt[a]);
        akt[a]=!akt[a];
    } else {
        //cout << a << " " << el[a]-1 << " " << cnt << " " << sz[cnt] << endl;
        if (!akt[a]) x[el[a]-1]=sz[cnt];
        else y[el[a]-1]=sz[cnt];
        cnt++, akt[a]=!akt[a];
    }
}
void create_circuit(int m, vector<int> p) {
    for (int i=0; i<m+1; i++) s.push_back(-1);
    sz=p, n=sz.size();
    if (n%2==0) sz.push_back(-1);
    sz.push_back(0), n=sz.size();
    while(po<n) po*=2; db=po, sw=po-1;
    dfs(1, po);
    x.resize(sw), y.resize(sw);
    dfs2(1), cnt=0;
    for (int i=0; i<po; i++) dfs3(1);
    /*for (int i=0; i<sw; i++) {
        cout << x[i] << " " << y[i] << "\n";
    }*/
    answer(s, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   39 |     while(po<n) po*=2; db=po, sw=po-1;
      |     ^~~~~
doll.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   39 |     while(po<n) po*=2; db=po, sw=po-1;
      |                        ^~

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