oj.uz

Submission #542819

# Submission time Handle Problem Language Result Execution time Memory
542819 2022-03-28T06:37:19 Z Sho10 Mechanical Doll (IOI18_doll) C++17
100 / 100
 121 ms 11936 KB 
#include "doll.h"
#include <iostream>
#include <vector>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
int const nmax = 400000;
int leftp[nmax+1];
int rightp[nmax+1];
int cng[nmax+1];
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[nmax+1];
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){
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(X[k-1]>=0){
        X[k-1]=real[X[k-1]];
    }
    if(Y[k-1]>=0){
            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:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 | for(int i=0;i<A.size();i++)
      |             ~^~~~~~~~~
doll.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 | while(nodes<dest.size()){
      |       ~~~~~^~~~~~~~~~~~
doll.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 | for(int i=0;i<dest.size();i++)
      |             ~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 39 ms 4948 KB Output is correct
3 Correct 38 ms 5084 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 58 ms 6868 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 0 ms 340 KB Output is correct
2 Correct 39 ms 4948 KB Output is correct
3 Correct 38 ms 5084 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 58 ms 6868 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 70 ms 8920 KB Output is correct
9 Correct 77 ms 9496 KB Output is correct
10 Correct 112 ms 11936 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 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 340 KB Output is correct
2 Correct 39 ms 4948 KB Output is correct
3 Correct 38 ms 5084 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 58 ms 6868 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 70 ms 8920 KB Output is correct
9 Correct 77 ms 9496 KB Output is correct
10 Correct 112 ms 11936 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 110 ms 11456 KB Output is correct
15 Correct 73 ms 8624 KB Output is correct
16 Correct 107 ms 11292 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 112 ms 11624 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 67 ms 7900 KB Output is correct
3 Correct 63 ms 7852 KB Output is correct
4 Correct 100 ms 10816 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 67 ms 7900 KB Output is correct
3 Correct 63 ms 7852 KB Output is correct
4 Correct 100 ms 10816 KB Output is correct
5 Correct 109 ms 11148 KB Output is correct
6 Correct 121 ms 11008 KB Output is correct
7 Correct 102 ms 11024 KB Output is correct
8 Correct 109 ms 10836 KB Output is correct
9 Correct 71 ms 7928 KB Output is correct
10 Correct 103 ms 10816 KB Output is correct
11 Correct 100 ms 10900 KB Output is correct
12 Correct 73 ms 8120 KB Output is correct
13 Correct 68 ms 8428 KB Output is correct
14 Correct 67 ms 8564 KB Output is correct
15 Correct 70 ms 8636 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 63 ms 7332 KB Output is correct
18 Correct 67 ms 8028 KB Output is correct
19 Correct 65 ms 8112 KB Output is correct
20 Correct 104 ms 10804 KB Output is correct
21 Correct 99 ms 10796 KB Output is correct
22 Correct 101 ms 10800 KB Output is correct