Submission #299459

#	Time	Username	Problem	Language	Result	Execution time	Memory
299459		DanerZein	Mechanical Doll (IOI18_doll)	C++14	53 / 100	286 ms	17564 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
int vis[400010],G[400010];
vi X,Y,C;
int sw=0;
map<int,int> m;
void create_switch(int x){
  int ns=2;
  queue<int> q;
  sw--;
  int insw=sw;
  q.push(sw);
  C[x]=insw;
  int aux=m[x];
  while(ns<aux){
    // cout<<ns<<endl;
    int t=q.size();
    for(int i=0;i<t;i++){
      ns-=2;
      int y=q.front();
      q.pop();
      X.push_back(sw-1);
      Y.push_back(sw-2);
      q.push(sw-1);
      q.push(sw-2);
      ns+=4;
      sw-=2;
    }
  }
  while(!q.empty()){
    int y=q.front();
    q.pop();
    if(ns>aux){
      X.push_back(insw); ns--;
      Y.push_back(-MAX);
      G[abs(y)]=-1;
    }
    else{
      X.push_back(-MAX);
      Y.push_back(-MAX);
    }
  }
}
bool sa=0;
int dfs(int u){
  u=abs(u);
  /*if(sw==-6)
    cout<<u<<" "<<X[abs(u)-1]<<" "<<Y[abs(u)-1]<<" "<<G[u]<<" "<<X.size()<<endl;*/
  if(G[u]==-1){
    G[u]=1;
    return dfs(abs(X[abs(u)-1]));
  }
  if(G[u]==1){
    G[u]=0;
    if(Y[abs(u)-1]==-MAX){
      sa=1; return abs(u)-1;
    }
    return dfs(Y[abs(u)-1]);
  }
  else{
    G[u]=1;
    if(X[abs(u)-1]==-MAX){sa=0; return abs(u)-1;}
    return dfs(X[abs(u)-1]);
  }
}
void create_circuit(int M, std::vector<int> A) {

  for(int i=0;i<A.size();i++){
    m[A[i]]++;
  }
  A.push_back(0);
  memset(vis,0,sizeof vis);
  memset(G,0,sizeof G);
  C.resize(M+1);
  C[0]=A[0];
  for(int i=0;i<A.size()-1;i++){
    if(m[A[i]]!=1){
      if(!vis[A[i]]){
	//cout<<A[i]<<endl;
	create_switch(A[i]);
	int ids=dfs(abs(C[A[i]]));
	if(sa==0) X[ids]=A[i+1];
	else Y[ids]=A[i+1];
	vis[A[i]]=1;
	//cout<<ids<<endl;
      }
      else{
	sa=0;
	int ids=dfs(abs(C[A[i]]));
	if(sa==0) X[ids]=A[i+1];
	else Y[ids]=A[i+1];
	//cout<<ids<<endl;
      }
      /*for(int i=0;i<=abs(sw);i++){
	cout<<G[i]<<" ";
      }
      cout<<endl;*/
      /* cout<<X.size()<<endl;*/
    }
    else{
      C[A[i]]=A[i+1];
    }
  }
  /* for(int i=0;i<C.size();i++){
    cout<<C[i]<<" ";
  }
  cout<<endl;
  cout<<X.size()<<" "<<Y.size()<<endl;*/
  /*for(int i=0;i<X.size();i++) cout<<X[i]<<" ";
  cout<<endl;
  for(int j=0;j<Y.size();j++) cout<<Y[j]<<" ";
  cout<<endl;*/
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_switch(int)':
doll.cpp:23:11: warning: unused variable 'y' [-Wunused-variable]
   23 |       int y=q.front();
      |           ^
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0;i<A.size();i++){
      |               ~^~~~~~~~~
doll.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<A.size()-1;i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56