Submission #624744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624744	2022-08-08T16:32:17 Z	evenvalue	Mechanical Doll (IOI18_doll)	C++17	16 / 100	81 ms	12556 KB

doll

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

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

vector<int> C;
vector<int> X;
vector<int> Y;

void connect(const int x, const vector<int> &next) {
  const int neighbours = (int) next.size();
  if (neighbours == 0) {
    C[x] = x;
  } else if (neighbours == 1) {
    C[x] = next[0];
  } else if (neighbours == 2) {
    X.push_back(next[0]);
    Y.push_back(next[1]);
    C[x] = -1 * (int) (X.size());
  } else if (neighbours == 3) {
    const int s1 = -1 * ((int) X.size() + 1);
    const int s2 = s1 - 1;
    const int s3 = s1 - 2;
    //C[x] connections
    C[x] = s1;
    //s1 connections
    X.push_back(s2);
    Y.push_back(s3);
    //s2 connections
    X.push_back(next[0]);
    Y.push_back(s1);
    //s3 connections
    X.push_back(next[1]);
    Y.push_back(next[2]);
  } else {
    const int s1 = -1 * ((int) X.size() + 1);
    const int s2 = s1 - 1;
    const int s3 = s1 - 2;
    //C[x] connections
    C[x] = s1;
    //s1 connections
    X.push_back(s2);
    Y.push_back(s3);
    //s2 connections
    X.push_back(next[0]);
    Y.push_back(next[2]);
    //s3 connections
    X.push_back(next[1]);
    Y.push_back(next[3]);
  }
}

void create_circuit(int m, std::vector<int> A) {
  const int n = A.size();

  C.resize(m + 1);
  vector<vector<int>> next(m + 1);
  next[0].push_back(A[0]);
  for (int i = 0; i < n - 1; i++) {
    next[A[i]].push_back(A[i + 1]);
  }
  next[A[n - 1]].push_back(0);

  for (int x = 0; x <= m; x++) {
    connect(x, next[x]);
  }
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	28 ms	6832 KB	Output is correct
3	Correct	20 ms	5544 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	14 ms	3796 KB	Output is correct
6	Correct	30 ms	8356 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	1 ms	212 KB	Output is correct
2	Correct	28 ms	6832 KB	Output is correct
3	Correct	20 ms	5544 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	14 ms	3796 KB	Output is correct
6	Correct	30 ms	8356 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	42 ms	8140 KB	Output is correct
9	Correct	45 ms	9496 KB	Output is correct
10	Correct	67 ms	12528 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	28 ms	6832 KB	Output is correct
3	Correct	20 ms	5544 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	14 ms	3796 KB	Output is correct
6	Correct	30 ms	8356 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	42 ms	8140 KB	Output is correct
9	Correct	45 ms	9496 KB	Output is correct
10	Correct	67 ms	12528 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	81 ms	12556 KB	Output is correct
15	Correct	41 ms	6792 KB	Output is correct
16	Correct	61 ms	10180 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	71 ms	12060 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct