Submission #301036

#	Time	Username	Problem	Language	Result	Execution time	Memory
301036		TMJN	Mechanical Doll (IOI18_doll)	C++17	6 / 100	287 ms	14588 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;
      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(y*2);
          Y.push_back((y*2)-1);
          q.push(y*2);
          q.push((y*2)-1);
          ns+=4;
          sw-=2;
        }
      }
      // cout<<ns<<endl;
      // cout<<sw<<endl;
      while(!q.empty()){
        //cout<<ns<<" "<<aux<<end;;
        int y=q.front();
        // cout<<y<<endl;
        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);
        }
      }
      // cout<<endl;
    }
    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:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       for(int i=0;i<A.size();i++){
      |                   ~^~~~~~~~~
doll.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |       for(int i=0;i<A.size()-1;i++){
      |                   ~^~~~~~~~~~~

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