Submission #1244760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244760		lncreedible	Mechanical Doll (IOI18_doll)	C++20	0 / 100	97 ms	18244 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    vector<vector<int>> occ(M + 1);
    for (int i = 0; i < N; ++i) occ[A[i]].push_back(i);

    vector<int> C(M + 1, 0);
    vector<int> X, Y;

    int sw_id = 1;
    map<int, int> head, tail;

    for (int t = 1; t <= M; ++t) {
        head[t] = sw_id++;
        tail[t] = head[t];
    }

    for (int t = 1; t <= M; ++t) {
        int sz = occ[t].size();
        for (int i = 2; i < sz; ++i) {
            int new_sw = sw_id++;
            tail[t] = new_sw;
        }
    }

    X.resize(sw_id);
    Y.resize(sw_id);

    C[0] = A[0];
    for (int t = 1; t <= M; ++t) {
        C[t] = -head[t];
    }

    for (int t = 1; t <= M; ++t) {
        auto& pos = occ[t];
        int sz = pos.size();
        if (sz == 0) continue;
        int cur = head[t];

        for (int i = 0; i < sz; ++i) {
            int nxt = (i + 1 < sz) ? -(head[t] + i + 1) : (pos[i] + 1 < N ? A[pos[i] + 1] : 0);
            X[cur] = -cur;
            Y[cur] = nxt;
            if (nxt < 0) cur = -nxt;
        }
    }

    for (int t = 1; t <= M; ++t) {
        int s = tail[t];
        if (!X[s]) X[s] = -s;
        if (!Y[s]) Y[s] = 0;
    }

    X.erase(X.begin());
    Y.erase(Y.begin());
    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