Submission #1111924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1111924	2024-11-13T11:10:01 Z	epicci23	Mechanical Doll (IOI18_doll)	C++17	16 / 100	62 ms	12960 KB

doll

#include "bits/stdc++.h"
#include "doll.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

vector<int> x,y,state,hm;
int p=0,p2=0;

void give_index(int rt,int l,int r){
  //if(rt<0) while(1){}
  if(l==r) return;
  x[rt] = ++p;
  y[rt] = ++p;
  int mid = (l+r)/2;
  give_index(x[rt],l,mid),give_index(y[rt],mid+1,r);
}

void give_index2(int rt,int l,int r){
  //if(rt<0) while(1){}
  if(l==r) return;
  int mid = (l+r)/2;
  give_index2(x[rt],l,mid),give_index2(y[rt],mid+1,r);
  x[rt] *= -1;
  y[rt] *= -1;
}

void make_leaf(int rt){
  //if(rt<0) while(1){}
  if(state[rt]==0){
    if(x[rt]==-1) x[rt]=hm[p2++];
    else make_leaf(x[rt]);
  }
  else{
    if(y[rt]==-1) y[rt]=hm[p2++];
    else make_leaf(y[rt]);
  }
  state[rt]^=1;
}

void create_circuit(int m, vector<int> a){
  int n = sz(a);
  vector<int> c(m+1);
  vector<int> adj[m+5];

  for(int i=0;i<n;i++){
    if(i==0) adj[0].push_back(a[i]);
    else adj[a[i-1]].push_back(a[i]);
  }
  adj[a.back()].push_back(0);
  
  x.push_back(-1);
  y.push_back(-1);
  state.push_back(0);

  for(int i=0;i<=m;i++){
    if(sz(adj[i])==0) c[i]=i;
    else if(sz(adj[i])==1) c[i]=adj[i][0];
    else if( sz(adj[i])==2 || sz(adj[i])==4 ){
      int xd = sz(adj[i]);
      int leaf=1;
      while(leaf<xd) leaf<<=1;
      int nd = leaf - 1;
      for(int j=0;j<nd;j++){
        x.push_back(-1);
        y.push_back(-1);
        state.push_back(0);
      }

      c[i] = ++p;
      give_index(c[i],1,leaf/2);

      p2=0;
      hm=adj[i];
      for(int j=0;j<xd;j++) make_leaf(c[i]);

      give_index2(c[i],1,leaf/2);
      c[i]*=-1;
    }
    else{

      for(int j=0;j<3;j++){
        x.push_back(-1);
        y.push_back(-1);
        state.push_back(0);
      }

      c[i] = -(++p);
      x[p]=-(p+1);
      y[p]=-(p+2);
      x[p+1]=adj[i][0];
      y[p+1]=-p;
      x[p+2]=adj[i][1];
      y[p+2]=adj[i][2];
      p+=2;
    }
  }

  reverse(all(x));
  x.pop_back();
  reverse(all(x));

  reverse(all(y));
  y.pop_back();
  reverse(all(y));

  answer(c, x, y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	19 ms	6480 KB	Output is correct
3	Correct	17 ms	5200 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	4092 KB	Output is correct
6	Correct	30 ms	7760 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	19 ms	6480 KB	Output is correct
3	Correct	17 ms	5200 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	4092 KB	Output is correct
6	Correct	30 ms	7760 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	34 ms	7752 KB	Output is correct
9	Correct	36 ms	8900 KB	Output is correct
10	Correct	53 ms	11580 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	19 ms	6480 KB	Output is correct
3	Correct	17 ms	5200 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	4092 KB	Output is correct
6	Correct	30 ms	7760 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	34 ms	7752 KB	Output is correct
9	Correct	36 ms	8900 KB	Output is correct
10	Correct	53 ms	11580 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	62 ms	12404 KB	Output is correct
15	Correct	36 ms	7212 KB	Output is correct
16	Correct	53 ms	10932 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Correct	57 ms	12960 KB	Output is correct
21	Correct	1 ms	504 KB	Output is correct
22	Correct	1 ms	336 KB	Output is correct