제출 #794068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794068		fatemetmhr	자동 인형 (IOI18_doll)	C++17	63 / 100	131 ms	73616 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define fi     first
#define se     second
#define pb     push_back

typedef long long ll;

const int maxn5 = 1e6 + 10;

int newnode = 0, pt[maxn5], cnt[maxn5];
vector <int> c, x, y;
vector <pair<int, int>> av[maxn5];

int build(int n){
    int rt = newnode++;
    x.pb(0);
    y.pb(0);
    if(n == 2){
        av[rt].pb({rt, 0});
        av[rt].pb({rt, 1});
        return rt;
    }
    int a = (n / 2);
    if(n & 1)
        a++;
    int r1 = build(a), r2 = build(a);
    x[rt] = -(r1 + 1);
    y[rt] = -(r2 + 1);
    //cout << "building " << n << ' ' << rt << ' ' << r1 << ' ' << r2 << ' ' << newnode << endl;
    for(int i = 0; i < a; i++){
        if(n % 2 && i == a - 1){
            if(av[r1][i].se)
                y[av[r1][i].fi] = -(rt + 1);
            else
                x[av[r1][i].fi] = -(rt + 1);
        }
        else
            av[rt].pb(av[r1][i]);
        av[rt].pb(av[r2][i]);
    }
    /*
    for(auto [u, v] : av[rt])
        cout << u << ' ' << v << endl;
    cout << "done " << x[rt] << ' ' << y[rt] << endl;
    //*/
    return rt;
}


void create_circuit(int m, std::vector<int> a) {
    int n = a.size();
    if(n == 1){
        c.pb(a[0]);
        for(int i = 0; i < m; i++)
            c.pb(0);
        answer(c, x, y);
        return;
    }
    int mx = 0;
    for(int i = 0; i < n; i++){
        cnt[a[i]]++;
        mx = max(mx, cnt[a[i]]);
    }
    if(mx <= 4){
        a.pb(0);
        c.resize(m + 1);
        c[0] = a[0];
        for(int i = 1; i <= m; i++){
            if(cnt[i] == 1)
                av[i].pb({-i, 0});
            if(cnt[i] == 2){
                c[i] = -(newnode + 1);
                av[i].pb({newnode, 0});
                av[i].pb({newnode, 1});
                newnode++;
                x.pb(0);
                y.pb(0);
            }
            if(cnt[i] == 3){
                c[i] = -(newnode + 1);
                newnode++;
                x.pb(-(newnode + 1));
                y.pb(-(newnode + 2));
                x.pb(0); x.pb(0);
                y.pb(c[i]); y.pb(0);
                av[i].pb({newnode, 0});
                av[i].pb({newnode + 1, 0});
                av[i].pb({newnode + 1, 1});
                newnode += 2;
            }
            if(cnt[i] == 4){
                c[i] = -(newnode + 1);
                newnode++;
                x.pb(-(newnode + 1));
                y.pb(-(newnode + 2));
                x.pb(0); x.pb(0);
                y.pb(0); y.pb(0);
                av[i].pb({newnode, 0});
                av[i].pb({newnode + 1, 0});
                av[i].pb({newnode, 1});
                av[i].pb({newnode + 1, 1});
                newnode += 2;
            }
        }

        for(int i = 0; i < n; i++){
            if(cnt[a[i]] == 1)
                c[a[i]] = a[i + 1];
            else{
                int u = a[i];
                if(av[u][pt[u]].se)
                    y[av[u][pt[u]].fi] = a[i + 1];
                else
                    x[av[u][pt[u]].fi] = a[i + 1];
                pt[u]++;
            }
        }
        answer(c, x, y);
        /*
        for(int i = 0; i < c.size(); i++)
            cout << c[i] << ' ';
        cout << endl;
        for(int i = 0; i < x.size(); i++)
            cout << x[i] << ' ' << y[i] << endl;
            //*/
        return;
    }

    build(n);
    c.pb(a[0]);
    for(int i = 0; i < m; i++)
        c.pb(-1);
    a.pb(0);
    for(int i = 0; i < n; i++){
        if(av[0][i].se)
            y[av[0][i].fi] = a[i + 1];
        else
            x[av[0][i].fi] = a[i + 1];
    }
    answer(c, x, y);
    /*
    for(auto u : c)
        cout << u << ' ';
    cout << endl;
    for(int i = 0; i < x.size(); i++)
        cout << x[i] << ' ' << y[i] << endl;
    //*/
    return;
}

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