Submission #320977

#	Time	Username	Problem	Language	Result	Execution time	Memory
320977		mhy908	Mechanical Doll (IOI18_doll)	C++14	2 / 100	83 ms	16052 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, m, arr[200010], cnt[100010], num[200010];
vector<int> vc[100010], ret1, ret2, ret3;
int conn[100010], re, sp[30][200010];
pii sw[200010];

void make_tree(int nw, int k, int nwnum, int rt, int skp, int lg, int tot, int c){
    if(k==2){
        int l=sp[lg][nwnum], r=sp[lg][nwnum+1];
        if(l<=skp)sw[nw].F=rt;
        else sw[nw].F=vc[c][l-skp-1];
        if(r<=skp)sw[nw].S=rt;
        else sw[nw].F=vc[c][r-skp-1];
        return;
    }
    re+=2;
    sw[nw]=mp(-re+1, -re);
    make_tree(sw[nw].F, k/2, nwnum, rt, skp, lg, tot, c);
    make_tree(sw[nw].S, k/2, nwnum+k/2, rt, skp, lg, tot, c);
}

void create_circuit(int M, vector<int> A){
    n=A.size(); m=M;
    for(int i=0; i<n; i++)arr[i+1]=A[i];
    for(int i=1; i<=n; i++){
        num[i]=++cnt[arr[i]];
        if(i!=n)vc[arr[i]].eb(arr[i+1]);
        else vc[arr[i]].eb(0);
    }
    sp[0][1]=1;
    for(int j=1; j<20; j++){
        for(int i=1; i<=(1<<j); i+=2)sp[j][i]=sp[j-1][2*i-1];
        for(int i=2; i<=(1<<j); i+=2)sp[j][i]=sp[j][i-1]+(1<<(j-1));
    }
    conn[0]=arr[1];
    for(int i=1; i<=m; i++){
        if(!cnt[i])continue;
        if(cnt[i]==1){
            conn[i]=vc[i][0];
            continue;
        }
        int sz, lg;
        for(sz=1, lg=0; sz<cnt[i]; sz*=2, lg++);
        ++re;
        conn[i]=-re;
        make_tree(++re, sz, 1, -re, sz-cnt[i], lg, sz, i);
    }
    for(int i=0; i<=m; i++)ret1.eb(conn[i]);
    for(int i=1; i<=re; i++)ret2.eb(sw[i].F);
    for(int i=1; i<=re; i++)ret3.eb(sw[i].S);
    answer(ret1, ret2, ret3);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:63:19: warning: operation on 're' may be undefined [-Wsequence-point]
   63 |         make_tree(++re, sz, 1, -re, sz-cnt[i], lg, sz, i);
      |                   ^~~~
doll.cpp:63:19: warning: operation on 're' may be undefined [-Wsequence-point]

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