Submission #764155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
764155	2023-06-23T07:53:49 Z	t6twotwo	Mechanical Doll (IOI18_doll)	C++17	16 / 100	54 ms	9388 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int M, vector<int> A) {
    int N = A.size();
    vector<int> f(M + 1);
    for (int i = 0; i < N; i++) {
        f[A[i]]++;
    }
    vector<int> S1(M + 1), S2(M + 1), S3(M + 1);
    int K = 0;
    for (int i = 1; i <= M; i++) {
        if (f[i] == 2) {
            S1[i] = K++;
        } else if (f[i] > 2) {
            S1[i] = K++;
            S2[i] = K++;
            S3[i] = K++;
        }
    }
    vector<int> X(K), Y(K), C(M + 1);
    for (int i = 1; i <= M; i++) {
        if (f[i] > 1) {
            C[i] = ~S1[i];
            if (f[i] > 2) {
                X[S1[i]] = ~S2[i];
                Y[S1[i]] = ~S3[i];
                if (f[i] == 3) {
                    Y[S2[i]] = ~S1[i];
                }
            }
        }
    }
    C[0] = A[0];
    vector<int> cnt(M + 1);
    for (int i = 0; i < N; i++) {
        if (f[A[i]] == 1) {
            C[A[i]] = i + 1 < N ? A[i + 1] : 0;
        } else if (f[A[i]] == 2) {
            if (cnt[A[i]] == 0) {
                X[S1[A[i]]] = A[i + 1];
            } else {
                Y[S1[A[i]]] = i + 1 < N ? A[i + 1] : 0;
            }
        } else if (f[A[i]] == 3) {
            if (cnt[A[i]] == 0) {
                X[S2[A[i]]] = A[i + 1];
            } else if (cnt[A[i]] == 1) {
                X[S3[A[i]]] = A[i + 1];
            } else {
                Y[S3[A[i]]] = i + 1 < N ? A[i + 1] : 0;
            }
        } else if (f[A[i]] == 4) {
            if (cnt[A[i]] == 0) {
                X[S2[A[i]]] = A[i + 1];
            } else if (cnt[A[i]] == 1) {
                X[S3[A[i]]] = A[i + 1];
            } else if (cnt[A[i]] == 2) {
                Y[S2[A[i]]] = A[i + 1];
            } else {
                Y[S3[A[i]]] = i + 1 < N ? A[i + 1] : 0;
            }
        }
        cnt[A[i]]++;
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	14 ms	3924 KB	Output is correct
3	Correct	12 ms	2900 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	9 ms	3412 KB	Output is correct
6	Correct	17 ms	4180 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	14 ms	3924 KB	Output is correct
3	Correct	12 ms	2900 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	9 ms	3412 KB	Output is correct
6	Correct	17 ms	4180 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	33 ms	4920 KB	Output is correct
9	Correct	28 ms	5428 KB	Output is correct
10	Correct	41 ms	7364 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	14 ms	3924 KB	Output is correct
3	Correct	12 ms	2900 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	9 ms	3412 KB	Output is correct
6	Correct	17 ms	4180 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	33 ms	4920 KB	Output is correct
9	Correct	28 ms	5428 KB	Output is correct
10	Correct	41 ms	7364 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	54 ms	8596 KB	Output is correct
15	Correct	31 ms	5592 KB	Output is correct
16	Correct	51 ms	8384 KB	Output is correct
17	Correct	1 ms	296 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	49 ms	9388 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct