Submission #139392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139392	2019-07-31T15:52:50 Z	wmrmr	Mechanical Doll (IOI18_doll)	C++17	16 / 100	132 ms	18092 KB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int MAX = 2e5+10; 
vector<int> g[MAX], ans, ansx, ansy;
int out[MAX], x[MAX], y[MAX];
int qtdS, n;
int New()
{
  int ret = -(++qtdS);
  return ret;
}
void Build(int v,vector<int> ord)
{
  int k = - v - 1;
  int grau = ord.size();
  if( grau == 2 )
  {
    x[k] = ord[0];
    y[k] = ord[1];
    return;
  }
  vector<int> first, second;
  if(grau % 2) 
  {
  	first.push_back( v ), second.push_back(ord[0]);
  	for(int i=1;i<grau;i++)
 	 {
  	 	int prox = ord[i];
  	 	if(i%2) first.push_back(prox);
  	 	else second.push_back(prox);
  	}
  }
  else
  {
  	for(int i=0;i<grau;i++)
  	{
  		int prox = ord[i];
  		if(i%2) second.push_back(prox);
  		else first.push_back(prox);
  	}
  }
  int n1 = New(), n2 = New();
  x[k] = n1; y[k] = n2;
  Build(n1,first); Build(n2,second);
  return;
}
void SetSwitch(int v)
{
  int grau = g[v].size();
  if(grau == 0){ out[v] = 0; return; }
  if(grau == 1){ out[v] = g[v][0]; return; }
  out[v] = New() ;
  Build( out[v], g[v] );
  return;
}
void create_circuit(int M, vector<int> A)
{
  n = A.size();
  g[0].push_back(A[0]); 
  for(int i=0;i<n-1;i++)
  {
    g[A[i]].push_back(A[i+1]);
  }
  g[A[n-1]].push_back(0);
  for(int i=0;i<=M;i++)
  {
    SetSwitch( i );
  }
  for(int i=0;i<=M;i++) ans.push_back(out[i]);
  for(int i=0;i<qtdS;i++) ansx.push_back(x[i]), ansy.push_back(y[i]);
  answer(ans,ansx,ansy);
  return;
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	46 ms	9172 KB	Output is correct
3	Correct	31 ms	8608 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	20 ms	6668 KB	Output is correct
6	Correct	44 ms	10572 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	46 ms	9172 KB	Output is correct
3	Correct	31 ms	8608 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	20 ms	6668 KB	Output is correct
6	Correct	44 ms	10572 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct
8	Correct	63 ms	11904 KB	Output is correct
9	Correct	65 ms	11828 KB	Output is correct
10	Correct	95 ms	14764 KB	Output is correct
11	Correct	4 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	46 ms	9172 KB	Output is correct
3	Correct	31 ms	8608 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	20 ms	6668 KB	Output is correct
6	Correct	44 ms	10572 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct
8	Correct	63 ms	11904 KB	Output is correct
9	Correct	65 ms	11828 KB	Output is correct
10	Correct	95 ms	14764 KB	Output is correct
11	Correct	4 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct
14	Correct	128 ms	17556 KB	Output is correct
15	Correct	67 ms	10800 KB	Output is correct
16	Correct	113 ms	13912 KB	Output is correct
17	Correct	6 ms	4940 KB	Output is correct
18	Correct	5 ms	4988 KB	Output is correct
19	Correct	4 ms	4940 KB	Output is correct
20	Correct	117 ms	16176 KB	Output is correct
21	Correct	4 ms	4940 KB	Output is correct
22	Correct	4 ms	4940 KB	Output is correct