Submission #284721

#	Time	Username	Problem	Language	Result	Execution time	Memory
284721		peti1234	Mechanical Doll (IOI18_doll)	C++17	0 / 100	427 ms	262148 KiB

doll

#include <bits/stdc++.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 (!v[a]) 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 {
        if (!akt[a]) x[el[a]-1]=sz[cnt];
        else y[el[a]-1]=sz[cnt];
        cnt++, akt[a]=!akt[a];
    }
}
auto create_circuit(int m, vector<int> p) {
    for (int i=0; i<m+1; i++) s.push_back(-1);
    sz=p;
    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(i);
    return(s, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'auto create_circuit(int, std::vector<int>)':
doll.cpp:36:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   36 |     while(po<n) po*=2; db=po, sw=po-1;
      |     ^~~~~
doll.cpp:36:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   36 |     while(po<n) po*=2; db=po, sw=po-1;
      |                        ^~
doll.cpp:41:12: warning: left operand of comma operator has no effect [-Wunused-value]
   41 |     return(s, x, y);
      |            ^
doll.cpp:41:18: warning: right operand of comma operator has no effect [-Wunused-value]
   41 |     return(s, x, y);
      |                  ^

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