Submission #284010

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284010	2020-08-26T12:29:14 Z	milleniumEeee	Mechanical Doll (IOI18_doll)	C++14	16 / 100	119 ms	12012 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;
 
int N, M, S;
vector <int> A, C, X, Y;
 
// A - sequance 
// C - edges of triggers
// X/Y - edges of switches
// M - triggers vertexes
 
void solve() {
  vector <vector<int>> after(M + 1);
  vector <int> cnt(M + 1, 0);
  A.push_back(0);
  for (int i = 1; i <= N; i++) {
    after[A[i]].push_back(A[i + 1]);
    cnt[A[i]]++;
  }
  int id = -1;
  for (int i = 1; i <= M; i++) {
    if (cnt[i] == 0) {
      continue;
    }
    if (cnt[i] == 1) {
      C[i] = after[i][0];
    }
    if (cnt[i] == 2) {
      C[i] = id;
      X.push_back(after[i][0]);
      Y.push_back(after[i][1]);
      id--;
    }
    if (cnt[i] == 3) {
      int a = id, b = id - 1, c = id - 2;
      C[i] = a;
      X.push_back(b); Y.push_back(c);
      X.push_back(a); Y.push_back(after[i][1]);
      X.push_back(after[i][0]); Y.push_back(after[i][2]);
      id -= 3;
    }
    if (cnt[i] == 4) {
      int a = id, b = id - 1, c = id - 2;
      C[i] = a;
      X.push_back(b); Y.push_back(c);
      X.push_back(after[i][0]); Y.push_back(after[i][2]);
      X.push_back(after[i][1]); Y.push_back(after[i][3]);
      id -= 3;
    }
  }
}

//3 6
//1 3 2 2 1 3

void create_circuit(int MM, vector<int> AA) {
  M = MM;
  N = AA.size();
  A.resize(N + 1);
  A[0] = 0;
  for (int i = 0; i < N; i++) {
    A[i + 1] = AA[i];
  }
  C.resize(M + 1);
  solve();
  C[0] = A[1];
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	32 ms	6216 KB	Output is correct
3	Correct	31 ms	5164 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	13 ms	3312 KB	Output is correct
6	Correct	61 ms	7628 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	32 ms	6216 KB	Output is correct
3	Correct	31 ms	5164 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	13 ms	3312 KB	Output is correct
6	Correct	61 ms	7628 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	54 ms	6696 KB	Output is correct
9	Correct	66 ms	8356 KB	Output is correct
10	Correct	101 ms	10144 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	2 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	32 ms	6216 KB	Output is correct
3	Correct	31 ms	5164 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	13 ms	3312 KB	Output is correct
6	Correct	61 ms	7628 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	54 ms	6696 KB	Output is correct
9	Correct	66 ms	8356 KB	Output is correct
10	Correct	101 ms	10144 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	2 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	101 ms	12012 KB	Output is correct
15	Correct	52 ms	6288 KB	Output is correct
16	Correct	103 ms	8796 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	2 ms	204 KB	Output is correct
20	Correct	119 ms	10076 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct