oj.uz

Submission #899223

# Submission time Handle Problem Language Result Execution time Memory
899223 2024-01-05T15:48:26 Z ThylOne Mechanical Doll (IOI18_doll) C++14
0 / 100
 0 ms 436 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
const int bonus = 4*100000;
const int flag = bonus-1;
struct node{
  int id=flag;
  int left=flag;
  int right=flag;
  int x=flag;
  int y=flag;
};
vector<node> pool;
vector<int> leafs;
void create_circuit(int M, std::vector<int> A) {

  //A.push_back(0);
  
  bool BAB = (__builtin_popcount(sz(A))==1);
  if(BAB)A.push_back(flag);
  int N = A.size();
  pool.resize(2*N);
  for(int i = 0;i<sz(pool);i++){
    pool[i].id = i;
  }
  for(int i=0;i<N/2+N%2;i++){
    leafs.push_back(i);
  }
  
  vector<int> actual = leafs;
  int actNode = N/2+N%2;
  while(actual.size()>1){
    if(actual.size()&1){
      actual.push_back(flag);
    }
    //dbg
    
    vector<int> vec;
    for(int i=0;i<sz(actual);i+=2){
      pool[actNode].left = actual[i];
      pool[actNode].right = actual[i+1];
      vec.push_back(actNode);
      actNode++;
    }
    swap(vec,actual);
  }
  
  for(int i=sz(leafs);i<sz(pool);i++){
    if((pool[i].left==flag)^(pool[i].right==flag)){
      if(pool[i].left==flag)
        pool[i].left=actNode;
      else
        pool[i].right=actNode;
      actNode++;
    }
  }
  pool.resize(actNode);
  
  int root = actual[0];
  
  //On coupe les branches en trop et on marque ce qu'on sait
  bool state[sz(pool)];
  fill(state,state+sz(pool),false);
  int tot=0;
  auto run = [&](){
    vector<int> way = {root};
    while(way.back()!=flag){
      //On flip now le state
      if(state[way.back()])tot--;
      else tot++;
      state[way.back()]=!state[way.back()];
      if(!state[way.back()]){
        //right
        way.push_back(pool[way.back()].right);
      }else{
        way.push_back(pool[way.back()].left);
      }
    }
    way.pop_back();
    return way.back();
  };
  
  int cnt=0;
  vector<int> last = {-1};
  int limit=0;
  
  for(int i=0;i<pool.size();i++){
    if(pool[i].left==flag)limit++;
    if(pool[i].right==flag)limit++;
  }
  for(int I=0;I<limit;I++){
    int r = run();
    if(r<leafs.size() && cnt<N){
      
      if(pool[r].x!=flag){
        pool[r].y = A[cnt];
      }else{
        pool[r].x = A[cnt];
      }
      //cout<<r<<' '<<A[cnt]<<endl;
      cnt++;
    }
    last.push_back(r);
  }
  pool[last.back()].y=0;
  
  vector<int> C;
  for(int i = 0;i<=M;i++){
    C.push_back(-(root+1));
  }
  vector<int> X,Y;
  for(int i=0;i<sz(leafs);i++){
    if(pool[i].x==flag)pool[i].x=-1-root;
    if(pool[i].y==flag)pool[i].y=-1-root;
    X.push_back(pool[i].x);
    Y.push_back(pool[i].y);
  }
  for(int i=sz(leafs);i<sz(pool);i++){
    if(pool[i].x==0){
      X.push_back(0);
    }else if(pool[i].left==flag){
      X.push_back(-1-root);
    }else{
      X.push_back(-1-pool[i].left);
    }
    if(pool[i].y==0){
      Y.push_back(0);
    }else if(pool[i].right==flag){
      Y.push_back(-1-root);
    }else{
      Y.push_back(-1-pool[i].right);
    }
  }
  
  

  answer(C,X,Y);
  
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:89:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int i=0;i<pool.size();i++){
      |               ~^~~~~~~~~~~~
doll.cpp:95:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     if(r<leafs.size() && cnt<N){
      |        ~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 436 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB wrong motion
2 Halted 0 ms 0 KB -