oj.uz

Submission #646547

# Submission time Handle Problem Language Result Execution time Memory
646547 2022-09-30T03:38:16 Z slime Mechanical Doll (IOI18_doll) C++14
100 / 100
 102 ms 11156 KB 
#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);
  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 2776 KB Output is correct
3 Correct 13 ms 2248 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1840 KB Output is correct
6 Correct 19 ms 3120 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 2776 KB Output is correct
3 Correct 13 ms 2248 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1840 KB Output is correct
6 Correct 19 ms 3120 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 56 ms 6464 KB Output is correct
9 Correct 61 ms 7128 KB Output is correct
10 Correct 93 ms 11156 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 1 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 2776 KB Output is correct
3 Correct 13 ms 2248 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1840 KB Output is correct
6 Correct 19 ms 3120 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 56 ms 6464 KB Output is correct
9 Correct 61 ms 7128 KB Output is correct
10 Correct 93 ms 11156 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 85 ms 10644 KB Output is correct
15 Correct 62 ms 7420 KB Output is correct
16 Correct 92 ms 10332 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 102 ms 10796 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 296 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 52 ms 5556 KB Output is correct
3 Correct 74 ms 5572 KB Output is correct
4 Correct 80 ms 8200 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 52 ms 5556 KB Output is correct
3 Correct 74 ms 5572 KB Output is correct
4 Correct 80 ms 8200 KB Output is correct
5 Correct 88 ms 8664 KB Output is correct
6 Correct 83 ms 8372 KB Output is correct
7 Correct 88 ms 8544 KB Output is correct
8 Correct 80 ms 8284 KB Output is correct
9 Correct 51 ms 5656 KB Output is correct
10 Correct 89 ms 8256 KB Output is correct
11 Correct 84 ms 8256 KB Output is correct
12 Correct 56 ms 5548 KB Output is correct
13 Correct 58 ms 5572 KB Output is correct
14 Correct 57 ms 5708 KB Output is correct
15 Correct 55 ms 5776 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 52 ms 5572 KB Output is correct
18 Correct 51 ms 5572 KB Output is correct
19 Correct 52 ms 5568 KB Output is correct
20 Correct 91 ms 8236 KB Output is correct
21 Correct 85 ms 8256 KB Output is correct
22 Correct 79 ms 8240 KB Output is correct