oj.uz

Submission #75460

# Submission time Handle Problem Language Result Execution time Memory
75460 2018-09-09T20:32:12 Z C_SUNSHINE Mechanical Doll (IOI18_doll) C++14
100 / 100
 125 ms 14828 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "doll.h"
using namespace std;

int N,M,H;
vector<int> C,X,Y,A,L,R;

vector<int> rem;

vector<int> idx;

int dfn[400005],cur[400005],S=0;

int bitreverse(int x)
{
  int t=0;
  for(int i=0;i<H;i++)
    t=(t<<1)|(x&1),x>>=1;
  return t;
}

int Get(int p)
{
  if(p==(1<<H)-1)return 0;
  if(p>=(1<<H)-1-N)
  {
    idx.push_back(bitreverse(p)+1);
    return bitreverse(p)+1;
  }
  return -1;
}

void dfs(int x)
{
  if(L[-x]<-1)dfs(L[-x]);
  if(R[-x]<-1)dfs(R[-x]);
  if(L[-x]==-1&&R[-x]==-1)rem[-x]=1;
  if(L[-x]<-1&&rem[-L[-x]]&&R[-x]<-1&&rem[-R[-x]])rem[-x]=1;
}

void label(int x)
{
  dfn[-x]=++S;
  if(L[-x]<-1&&!rem[-L[-x]])label(L[-x]);
  if(R[-x]<-1&&!rem[-R[-x]])label(R[-x]);
}

void calc(int x)
{
  if(L[-x]<-1&&!rem[-L[-x]])
  {
    X[dfn[-x]-1]=-dfn[-L[-x]];
    calc(L[-x]);
  }
  else if(L[-x]>=0)
    X[dfn[-x]-1]=cur[L[-x]];
  else
    X[dfn[-x]-1]=-1;
  if(R[-x]<-1&&!rem[-R[-x]])
  {
    Y[dfn[-x]-1]=-dfn[-R[-x]];
    calc(R[-x]);
  }
  else if(R[-x]>=0)
    Y[dfn[-x]-1]=cur[R[-x]];
  else
    Y[dfn[-x]-1]=-1;
}

void create_circuit(int M, std::vector<int> A)
{
  N=A.size();
  ::M=M;
  ::A=A;
  C.assign(M+1,-1);
  for(H=0;(1<<H)<=N;H++);
  L.assign((1<<H),0);
  R.assign((1<<H),0);
  for(int i=1;i<(1<<H);i++)
  {
    if(i*2<(1<<H))
    {
      L[i]=-(i*2);
      R[i]=-(i*2+1);
    }
    else
    {
      L[i]=Get(i*2-(1<<H));
      R[i]=Get(i*2+1-(1<<H));
    }
  }
  
  rem.assign((1<<H),0);
  dfs(-1);
  label(-1);
  //for(int i=1;i<(1<<H);i++)cout<<dfn[i]<<' ';cout<<endl;
  sort(idx.begin(),idx.end());
  for(int i=0;i<idx.size();i++)
    cur[idx[i]]=A[i];
  X.assign(S,0);
  Y.assign(S,0);
  calc(-1);
  
  if(X.size()>N*2)while(1);
  //for(int i=0;i<C.size();i++)cout<<C[i]<<' ';cout<<endl;
  //for(int i=0;i<X.size();i++)cout<<X[i]<<' '<<Y[i]<<endl;
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i=0;i<idx.size();i++)
      |               ~^~~~~~~~~~~
doll.cpp:109:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |   if(X.size()>N*2)while(1);
      |      ~~~~~~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 6464 KB Output is correct
3 Correct 41 ms 6768 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 63 ms 7980 KB Output is correct
7 Correct 2 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 49 ms 6464 KB Output is correct
3 Correct 41 ms 6768 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 63 ms 7980 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 76 ms 11252 KB Output is correct
9 Correct 78 ms 12724 KB Output is correct
10 Correct 121 ms 14828 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 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 1 ms 204 KB Output is correct
2 Correct 49 ms 6464 KB Output is correct
3 Correct 41 ms 6768 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 63 ms 7980 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 76 ms 11252 KB Output is correct
9 Correct 78 ms 12724 KB Output is correct
10 Correct 121 ms 14828 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 115 ms 14344 KB Output is correct
15 Correct 75 ms 11700 KB Output is correct
16 Correct 125 ms 14052 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 120 ms 14472 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 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 204 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 67 ms 10244 KB Output is correct
3 Correct 77 ms 10676 KB Output is correct
4 Correct 113 ms 13088 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 67 ms 10244 KB Output is correct
3 Correct 77 ms 10676 KB Output is correct
4 Correct 113 ms 13088 KB Output is correct
5 Correct 125 ms 13956 KB Output is correct
6 Correct 110 ms 13620 KB Output is correct
7 Correct 116 ms 13712 KB Output is correct
8 Correct 108 ms 13312 KB Output is correct
9 Correct 69 ms 10708 KB Output is correct
10 Correct 109 ms 13300 KB Output is correct
11 Correct 106 ms 13112 KB Output is correct
12 Correct 73 ms 10936 KB Output is correct
13 Correct 80 ms 10332 KB Output is correct
14 Correct 76 ms 11428 KB Output is correct
15 Correct 75 ms 11616 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 68 ms 8116 KB Output is correct
18 Correct 68 ms 10232 KB Output is correct
19 Correct 76 ms 10996 KB Output is correct
20 Correct 106 ms 13188 KB Output is correct
21 Correct 105 ms 13088 KB Output is correct
22 Correct 120 ms 13164 KB Output is correct