Submission #646803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646803	2022-09-30T17:34:05 Z	slime	Mechanical Doll (IOI18_doll)	C++14	92.5999 / 100	92 ms	9652 KB

doll

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

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

int lg(int x) {
  return 32 - __builtin_clz(x) - 1;
}
vector<int> X, Y;

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();

  int freq[M+1];
  for(int i=1; i<=M; i++) freq[i] = 0;

  for(int i=0; i<N; i++) freq[A[i]]++;

  int ma = 0;
  for(int i=1; i<=M; i++) ma = max(ma, freq[i]);
  vector<int> C(M + 1);
  for(int i=0; i<=M; i++) C[i] = 0;
  C[0] = A[0];
  vector<int> sequence;
  vector<int> empty;
  for(int i=0; i+1<N; i++) {
    sequence.push_back(A[i+1]);
  }
  
  if(ma <= 1) {
    for(int i=0; i<N; i++) C[A[i]] = (i+1 == N ? 0 : A[i+1]);
    answer(C, empty, empty);
    return; 
  }
  for(int i=1; i<=M; i++) C[i] = -1;
  if(N % 2 == 0) sequence.push_back(-1);
  if(ma <= 4 || N == 16) {
    X.resize(N + lg(N));
    Y.resize(N + lg(N));
  }
  else if(M == 1) {
    if(N >= 200000) {
      X.resize(N + lg(N) + 1);
      Y.resize(N + lg(N) + 1);
    }
    else {
      X.resize(N + lg(N));
      Y.resize(N + lg(N));
    }
  }
  else {
    X.resize(N + lg(N));
    Y.resize(N + lg(N));
  }
  int L = sequence.size();
  
  int bitcount = 1 + lg(L);
  int nxt = 0;
  int uwu = bitcount;
  for(int i=bitcount-1; i>=0; i--) {
    int val = (1 << i);
    Y[nxt] = (i == 0 ? 12073412 : nxt+1);
    // tree of size val: val - 1 swithces
    if(!(L & (1 << i))) X[nxt] = 0;
    else X[nxt] = uwu;
    nxt++;
    if(!(L & (1 << i))) continue;
    int seq = uwu + 1;
    for(int j=uwu; j<uwu+val/2-1; j++) {
      X[j] = seq;
      seq++;
      Y[j] = seq;
      seq++;
    }
    for(int j=uwu+val/2-1; j<uwu+val-1; j++) {
      X[j] = Y[j] = -1;
    }
    uwu += val - 1;
  }

  // Non-negative: switch
  // -1: to-be trigger
  // -2: origin

  int id = 0;
  int visits = 0;
  int state[N + lg(N)];
  for(int i=0; i<N+lg(N); i++) state[i] = 0;


  while(1) {
    int cur = 0;
    int prv;
    char u;
    bool done = 0;
    while(1) {
      //if(cur == 12073412) cout << "end\n";
      //else if(cur != -1) cout << -(cur + 1) << "\n";
      if(cur == -1) {
        if(u == 'X') X[prv] = -(sequence[id] + 1);
        else Y[prv] = -(sequence[id] + 1);
       // cout << sequence[id] << "\n";
        id++;
        break;
      }
      else if(cur == 12073412) {
        done = 1;
        break;
      }
      else if(state[cur] == 0) {
        state[cur] ^= 1;
        prv = cur;
        u = 'X';
        cur = X[cur];
      }
      else {
        state[cur] ^= 1;
        prv = cur;
        u = 'Y';
        cur = Y[cur];
      }
    }
    visits++;
    if(done) break;
  }


  for(int i=0; i<N+lg(N); i++) {
    if(X[i] == 12073412) X[i] = 0;
    else X[i] = -(X[i] + 1);
    if(Y[i] == 12073412) Y[i] = 0;
    else Y[i] = -(Y[i] + 1);
  }


//  for(int i=0; i<N+lg(N); i++) cout << state[i];
 // cout << "\n";

  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	16 ms	2764 KB	Output is correct
3	Correct	13 ms	2256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	9 ms	1748 KB	Output is correct
6	Correct	22 ms	3124 KB	Output is correct
7	Correct	0 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	16 ms	2764 KB	Output is correct
3	Correct	13 ms	2256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	9 ms	1748 KB	Output is correct
6	Correct	22 ms	3124 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	59 ms	6468 KB	Output is correct
9	Correct	60 ms	7124 KB	Output is correct
10	Correct	92 ms	9652 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	0 ms	212 KB	Output is correct
2	Correct	16 ms	2764 KB	Output is correct
3	Correct	13 ms	2256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	9 ms	1748 KB	Output is correct
6	Correct	22 ms	3124 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	59 ms	6468 KB	Output is correct
9	Correct	60 ms	7124 KB	Output is correct
10	Correct	92 ms	9652 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	91 ms	9136 KB	Output is correct
15	Correct	56 ms	6548 KB	Output is correct
16	Correct	86 ms	8880 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	89 ms	9280 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct

Subtask #5

16.1999718912 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	51 ms	5576 KB	Output is correct
3	Correct	51 ms	5560 KB	Output is correct
4	Partially correct	80 ms	8204 KB	Output is partially correct

Subtask #6

50.3999125504 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	51 ms	5576 KB	Output is correct
3	Correct	51 ms	5560 KB	Output is correct
4	Partially correct	80 ms	8204 KB	Output is partially correct
5	Correct	85 ms	8744 KB	Output is correct
6	Correct	83 ms	8384 KB	Output is correct
7	Correct	83 ms	8516 KB	Output is correct
8	Correct	89 ms	8256 KB	Output is correct
9	Correct	51 ms	5532 KB	Output is correct
10	Correct	81 ms	8252 KB	Output is correct
11	Correct	80 ms	8204 KB	Output is correct
12	Correct	51 ms	5572 KB	Output is correct
13	Correct	53 ms	5676 KB	Output is correct
14	Correct	55 ms	5732 KB	Output is correct
15	Correct	55 ms	5776 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	50 ms	5580 KB	Output is correct
18	Correct	51 ms	5564 KB	Output is correct
19	Correct	51 ms	5560 KB	Output is correct
20	Correct	84 ms	8224 KB	Output is correct
21	Correct	83 ms	8188 KB	Output is correct
22	Correct	81 ms	8204 KB	Output is correct