답안 #1111923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111923	2024-11-13T11:08:38 Z	epicci23	자동 인형 (IOI18_doll)	C++17	6 / 100	59 ms	11692 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];
    }
  }

  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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	22 ms	6480 KB	Output is correct
3	Correct	19 ms	5368 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	3920 KB	Output is correct
6	Correct	28 ms	7760 KB	Output is correct
7	Correct	1 ms	504 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	22 ms	6480 KB	Output is correct
3	Correct	19 ms	5368 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	3920 KB	Output is correct
6	Correct	28 ms	7760 KB	Output is correct
7	Correct	1 ms	504 KB	Output is correct
8	Correct	35 ms	7752 KB	Output is correct
9	Correct	35 ms	9076 KB	Output is correct
10	Correct	53 ms	11572 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	568 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	22 ms	6480 KB	Output is correct
3	Correct	19 ms	5368 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	10 ms	3920 KB	Output is correct
6	Correct	28 ms	7760 KB	Output is correct
7	Correct	1 ms	504 KB	Output is correct
8	Correct	35 ms	7752 KB	Output is correct
9	Correct	35 ms	9076 KB	Output is correct
10	Correct	53 ms	11572 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	568 KB	Output is correct
14	Incorrect	59 ms	11692 KB	wrong motion
15	Halted	0 ms	0 KB	-