제출 #964107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964107		dong_gas	Mechanical Doll (IOI18_doll)	C++17	0 / 100	2 ms	4704 KiB

doll

#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/extc++.h>
#include "doll.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, m, idx, r, h;
int num[400040], nxt[400040][2];
vector<tuple<int,int,int>> leaves;

void go(int N, int depth, int v) {
    if(!r) return;
    if(depth>h) return;
    //v: 순서
    int pivot=1<<depth;
    num[N]=++idx;
    if(depth+1==h) {
        nxt[idx][0]=nxt[idx][1]=-1;
        leaves.push_back({v,idx,0});
        leaves.push_back({v|pivot,idx,1});
        r--;
        return;
    }
    go(2*N,depth+1,v);
    nxt[num[N]][0]= num[2*N] ? -num[2*N] : -1;
    go(2*N+1,depth+1,v|pivot);
    //if(num[N]==5) cout<<num[2*N+1]<<endl;
    nxt[num[N]][1]= num[2*N+1] ? -num[2*N+1] : -1;
    //cout<<num[N]<<' '<<nxt[num[N]][0]<<' '<<nxt[num[N]][1]<<endl;
}

void create_circuit(int M, vector<int> a) {
    m=M, n=a.size(), r=n+1;
    while((1<<h) < r) h++;
    //cout<<h<<endl;
    r=n/2+1;
    memset(nxt,-1,sizeof(nxt));
    //memset(num,-1,sizeof(num));
    go(1,0,0);
    sort(all(leaves));
    
    for(int i=0;i<=n;i++) {
        auto [o, k, dir] = leaves[i];
        //cout<<o<<' '<<k<<' '<<dir<<endl;
        if(i<n) nxt[k][dir]=a[i];
        else nxt[k][dir]=0;
    }
    
    
    vector<int> c(m+1,-1), x(idx), y(idx);
    for(int i=0;i<idx;i++) x[i]=nxt[i+1][0], y[i]=nxt[i+1][1];
    answer(c,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