Submission #286137

#	Time	Username	Problem	Language	Result	Execution time	Memory
286137		NONAME	Mechanical Doll (IOI18_doll)	C++14	6 / 100	104 ms	12556 KiB

doll

#include "doll.h"

const int MAX_M = (int)(1e5 + 500);

std::vector <int> res, X, Y;
std::vector <int> g[MAX_M];

void create_circuit (int m, std::vector <int> a) {
    int n = (int)(a.size());
    
    res.resize(m + 1);
    res[0] = a[0];
    
    for (int i = 0; i < n; ++i)
        g[a[i]].push_back((i + 1 == n) ? 0 : a[i + 1]);

    int cur = -1;
    for (int i = 1; i <= m; ++i) {
        if ((int)(g[i].size()) == 1)
            res[i] = g[i][0];

        if ((int)(g[i].size()) == 2) {
            res[i] = cur;
            X.push_back(g[i][0]);
            Y.push_back(g[i][1]);
            --cur;
        }

        if ((int)(g[i].size()) == 3) {
            res[i] = cur;
            X.push_back(cur - 1);
            Y.push_back(cur - 2);
            X.push_back(cur);
            Y.push_back(g[i][1]);
            X.push_back(g[i][0]);
            Y.push_back(g[i][2]);
            cur -= 3;
        }
    }
    
    answer(res, X, Y);
}

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