oj.uz

Submission #153969

# Submission time Handle Problem Language Result Execution time Memory
153969 2019-09-17T15:27:59 Z AlexLuchianov Mechanical Doll (IOI18_doll) C++14
100 / 100
 189 ms 11564 KB 
#include "doll.h"
#include <iostream>
#include <vector>

#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 400000;
int leftp[1 + nmax];
int rightp[1 + nmax];
int cng[1 + nmax];

int switches = 0, added = 0;

int creategraph(int nodes, int realnodes){
  if(realnodes == 0)
    return -1;

  if(nodes == 1)
    return (added++);

  int central = -(++switches);

  leftp[-central] = creategraph(nodes / 2, realnodes - MIN(nodes / 2, realnodes));
  rightp[-central] = creategraph(nodes / 2, MIN(nodes / 2, realnodes));
  return central;
}

std::vector<int> dest;

int real[1 + nmax];

int dfs(int node){
  if(0 <= node)
    return node;
  else{
    cng[-node] = !cng[-node];
    if(cng[-node] == 1)
      return dfs(leftp[-node]);
    else
      return dfs(rightp[-node]);
  }
}

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

  int N = A.size();
  std::vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i)
    C[i] = -1;

  for(int i = 0; i < A.size(); i++)
    dest.push_back(A[i]);
  dest.push_back(0);
  int nodes = 1;
  while(nodes < dest.size())
    nodes *= 2;

  creategraph(nodes, dest.size());

  for(int i = 0; i < dest.size(); i++)
    real[dfs(-1)] = dest[i];

  std::vector<int> X(switches), Y(switches);

  for (int k = 1; k <= switches; ++k) {
    X[k - 1] = leftp[k];
    Y[k - 1] = rightp[k];

    if(0 <= X[k - 1])
      X[k - 1] = real[X[k - 1]];
    if(0 <= Y[k - 1])
      Y[k - 1] = real[Y[k - 1]];
  }

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   while(nodes < dest.size())
      |         ~~~~~~^~~~~~~~~~~~~
doll.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i < dest.size(); i++)
      |                  ~~^~~~~~~~~~~~~
doll.cpp:48:7: warning: unused variable 'N' [-Wunused-variable]
   48 |   int N = A.size();
      |       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4924 KB Output is correct
3 Correct 52 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 71 ms 6716 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 1 ms 204 KB Output is correct
2 Correct 51 ms 4924 KB Output is correct
3 Correct 52 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 71 ms 6716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 8792 KB Output is correct
9 Correct 97 ms 9256 KB Output is correct
10 Correct 141 ms 11564 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4924 KB Output is correct
3 Correct 52 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 71 ms 6716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 8792 KB Output is correct
9 Correct 97 ms 9256 KB Output is correct
10 Correct 141 ms 11564 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 154 ms 11180 KB Output is correct
15 Correct 95 ms 8524 KB Output is correct
16 Correct 135 ms 11072 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 140 ms 11444 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 86 ms 7648 KB Output is correct
3 Correct 81 ms 7596 KB Output is correct
4 Correct 129 ms 10556 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 86 ms 7648 KB Output is correct
3 Correct 81 ms 7596 KB Output is correct
4 Correct 129 ms 10556 KB Output is correct
5 Correct 137 ms 10896 KB Output is correct
6 Correct 137 ms 10656 KB Output is correct
7 Correct 177 ms 10816 KB Output is correct
8 Correct 132 ms 10608 KB Output is correct
9 Correct 99 ms 7596 KB Output is correct
10 Correct 133 ms 10576 KB Output is correct
11 Correct 127 ms 10536 KB Output is correct
12 Correct 95 ms 7856 KB Output is correct
13 Correct 85 ms 8240 KB Output is correct
14 Correct 85 ms 8344 KB Output is correct
15 Correct 86 ms 8492 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 82 ms 7116 KB Output is correct
18 Correct 84 ms 7844 KB Output is correct
19 Correct 88 ms 7880 KB Output is correct
20 Correct 189 ms 10548 KB Output is correct
21 Correct 141 ms 10544 KB Output is correct
22 Correct 125 ms 10548 KB Output is correct