제출 #427427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427427		Aldas25	자동 인형 (IOI18_doll)	C++14	16 / 100	181 ms	30220 KiB

doll

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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int INF = 1e9;

void create_circuit(int m, vi a) {
    int n = a.size();
    a.pb(0);
    vi C(m + 1);
    C[0] = a[0];
    for (int i = 1; i <= m; ++i) {
        C[i] = 0;
    }

    vector<vi> tmp(m+1);
    FOR(i, 0, n-1) {
        tmp[a[i]].pb(a[i+1]);
    }
    vector<vi> out;
    vi pr;
    vi X, Y;
//cout << " hh" << endl;
    FOR(i, 1, m) {
  //      cout << " i = " << i << endl;
        vi cur;
        cur.pb(i);
    //    cout << " asdaasdasd s " << endl;
        for (int xx : tmp[i]) {
      //      cout << "    pushing xx = " << xx << endl;
            cur.pb(xx);
        //    cout << "   after pu" << endl;
        }
       // cout <<"  asdffsfsdfsdfsdfds" << endl;
        out.pb(cur);
    }
//cout << " asdas" << endl;
    FOR(i, 0, (int)out.size()-1) {
  //      cout << " i=" << i << endl;
        vi cur = out[i];
        out[i].clear();
        //cout << " cur: ";
        //for (int xx : cur) cout << xx << " ";
        //cout << endl;

        int id = cur[0];
        if ((int)cur.size() == 1) {
            if (id > 0) C[id] = 0;
            else if (id < 0) X[abs(id)] = id, Y[abs(id)] = 0;
            continue;
        }
        if ((int)cur.size() == 2) {
            int to = cur[1];
            if (id > 0) C[id] = to;
            else if (id < 0) X[abs(id)] = id, Y[abs(id)] = to;
            continue;
        }

        if (id > 0) {
            vi nw;
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(id);
            nw.pb(-scnt);
            C[id] = -scnt;
            FOR(j, 1, (int)cur.size()-1) nw.pb(cur[j]);
            out.pb(nw);
            continue;
        }

        vi one, two;
        //int scnt = (int)X.size();
        //scnt++;
        //REP(2) {X.pb(0); Y.pb(0);}
        bool b = false;
        //X[id] = -scnt;
        //Y[id] =
        //one.pb(-scnt);
        //two.pb(-(scnt+1));

        int twoPwr = 1;
        while (twoPwr < (int)cur.size()-1) {
            twoPwr *= 2;
        }

        REP(twoPwr - (int)cur.size()+1) {
            if (!b)
                one.pb(INF);
            else
                two.pb(INF);
            b = !b;
        }

        FOR(j, 1, (int)cur.size()-1) {
            if (!b)
                one.pb(cur[j]);
            else
                two.pb(cur[j]);

            b = !b;
        }

        if ((int)one.size() == 1) X[abs(id)-1] = one[0];
        else {
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(id);
            X[abs(id)-1] = -scnt;
            reverse(one.begin(), one.end());
            one.pb(-scnt);
            reverse(one.begin(), one.end());
            out.pb(one);
        }

        if ((int)two.size() == 1) Y[abs(id)-1] = two[0];
        else {
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(id);
            Y[abs(id)-1] = -scnt;
            reverse(two.begin(), two.end());
            two.pb(-scnt);
            reverse(two.begin(), two.end());
            out.pb(two);
        }

        //out.pb(one);
        //out.pb(two);
    }

    FOR(i, 0, (int)X.size()-1) {
        if (X[i] == INF) X[i] = pr[i];
        if (Y[i] == INF) Y[i] = pr[i];
    }

    answer(C, X, Y);
}

/*

4 4
1 2 1 3

*/

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