Submission #299392

#	Time	Username	Problem	Language	Result	Execution time	Memory
299392		DanerZein	Mechanical Doll (IOI18_doll)	C++14	2 / 100	123 ms	14556 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
int vis[100010],G[200010];
vi X,Y,C;
int sw=0;
map<int,int> m;
void create_switch(int x){
  int ns=2;
  queue<int> q;
  int insw=sw-1;
  q.push(sw-1);
  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(y*2);
      Y.push_back((y*2)-1);
      q.push(y*2);
      q.push((y*2)-1);
      ns+=4;
      sw=min(sw,(y*2)-1);
    }
  }
  // cout<<sw<<endl;
  while(!q.empty()){
    //cout<<ns<<" "<<aux<<endl;
    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){
  //cout<<u<<" "<<X[abs(u)-1]<<" "<<Y[abs(u)-1]<<" "<<G[u]<<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(abs((u*2)+1));
  }
  else{
    G[u]=1;
    if(X[abs(u)-1]==-MAX){sa=0; return abs(u)-1;}
    return dfs(abs(u*2));
  }
}
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]]){
	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;*/
    }
    else{
      C[A[i]]=A[i+1];
    }
  }
  
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=0;i<A.size();i++){
      |               ~^~~~~~~~~
doll.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0;i<A.size()-1;i++){
      |               ~^~~~~~~~~~~

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