Submission #139249

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139249	2019-07-31T13:26:02 Z	qrno	Mechanical Doll (IOI18_doll)	C++14	16 / 100	130 ms	13932 KB

doll

#include "doll.h"

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

const int MAXN = 100100;
const int INF = 123456;
const int SELF = 123321;

vector<int> X, Y;

vector<int> neigh[MAXN];

bool secondTime[MAXN];
    
int sCount = -1;
int createSwitch(int x, int y) {
    X.push_back(x);
    Y.push_back(y);

    if (x == SELF)
        X[-sCount] = sCount;
    if (y == SELF)
        Y[-sCount] = sCount;
    
    return sCount--;
}

void printAns(vector<int> C, vector<int> X, vector<int> Y) {
    cout << "C: ";
    for (int x : C)
        cout << x << " ";
    cout << endl;

    cout << "(X, Y): ";
    for (int i = 0; i < (int)X.size(); i++) {
        cout << "(" << X[i] << ", "
            << Y[i] << ") ";
    }
    cout << endl;
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M + 1, INF);

    A.push_back(0);

    memset(secondTime, false, sizeof(secondTime));

    for (int i = 0; i < (int)A.size()-1; i++) {
        neigh[A[i]].push_back(A[i+1]);
    }

    C[0] = A[0];
    for (int i = 1; i <= M; i++) {
        int na = neigh[i].size();
        if (na == 0) {
            C[i] = 0;
        } else if (na == 1) {
            C[i] = neigh[i][0];
        } else if (na == 2) {
            C[i] = createSwitch(neigh[i][0],
                    neigh[i][1]);
        } else if (na == 3) {
            int s1 = createSwitch(neigh[i][1], neigh[i][2]);
            int s2 = createSwitch(neigh[i][0], sCount-1);
            int s3 = createSwitch(s2, s1);

            C[i] = s3;
        } else if (na == 4) {
            C[i] = createSwitch(createSwitch(neigh[i][0], neigh[i][2]),
                    createSwitch(neigh[i][1], neigh[i][3]));
        }
    }

    for (int i = 1; i <= M; i++) {
        if (C[i] == INF)
            C[i] = 0;
    }

    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2656 KB	Output is correct
2	Correct	36 ms	6436 KB	Output is correct
3	Correct	31 ms	6036 KB	Output is correct
4	Correct	3 ms	2636 KB	Output is correct
5	Correct	18 ms	3916 KB	Output is correct
6	Correct	41 ms	7740 KB	Output is correct
7	Correct	2 ms	2636 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2656 KB	Output is correct
2	Correct	36 ms	6436 KB	Output is correct
3	Correct	31 ms	6036 KB	Output is correct
4	Correct	3 ms	2636 KB	Output is correct
5	Correct	18 ms	3916 KB	Output is correct
6	Correct	41 ms	7740 KB	Output is correct
7	Correct	2 ms	2636 KB	Output is correct
8	Correct	57 ms	8632 KB	Output is correct
9	Correct	83 ms	8904 KB	Output is correct
10	Correct	126 ms	12096 KB	Output is correct
11	Correct	3 ms	2636 KB	Output is correct
12	Correct	3 ms	2724 KB	Output is correct
13	Correct	4 ms	2636 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2656 KB	Output is correct
2	Correct	36 ms	6436 KB	Output is correct
3	Correct	31 ms	6036 KB	Output is correct
4	Correct	3 ms	2636 KB	Output is correct
5	Correct	18 ms	3916 KB	Output is correct
6	Correct	41 ms	7740 KB	Output is correct
7	Correct	2 ms	2636 KB	Output is correct
8	Correct	57 ms	8632 KB	Output is correct
9	Correct	83 ms	8904 KB	Output is correct
10	Correct	126 ms	12096 KB	Output is correct
11	Correct	3 ms	2636 KB	Output is correct
12	Correct	3 ms	2724 KB	Output is correct
13	Correct	4 ms	2636 KB	Output is correct
14	Correct	109 ms	13932 KB	Output is correct
15	Correct	74 ms	8400 KB	Output is correct
16	Correct	99 ms	11208 KB	Output is correct
17	Correct	3 ms	2636 KB	Output is correct
18	Correct	3 ms	2656 KB	Output is correct
19	Correct	3 ms	2636 KB	Output is correct
20	Correct	130 ms	12540 KB	Output is correct
21	Correct	3 ms	2636 KB	Output is correct
22	Correct	3 ms	2636 KB	Output is correct