Submission #235801

#	Time	Username	Problem	Language	Result	Execution time	Memory
235801		DanerZein	Gondola (IOI14_gondola)	C++14	35 / 100	25 ms	2296 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define MAX 100000000
#define mod 1000000009
using namespace std;
typedef pair<int,int> ii;
int valid(int n, int inputSeq[])
{
  set<int>s;
  int id,mi;
  mi=MAX;
  id=0;
  for(int i=0;i<n;i++){
    if(mi>inputSeq[i]){
      id=i;
      mi=inputSeq[i];
    }
    s.insert(inputSeq[i]);
  }
  bool sw=0;
  int vis[100000];
  memset(vis,0,sizeof vis);
  if(mi<=n){
    int j=id;
    int aux=mi;
    while(true){
      if(vis[j]!=0) break;
      if(j==n+1) j=0;
      if(aux==n+1) aux=1;
      if(inputSeq[j]<=n){
	if(inputSeq[j]!=aux) return 0;
      }
      vis[j]=1;
      j++;
      aux++;
    }
    if(s.size()!=n) return 0;
    return 1;
  }
  if(s.size()==n) return 1;
  else return 0;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector<bool> nf(250010,false);
  vector<ii> gn;
  int mi=MAX,id;
  for(int i=0;i<n;i++){
    if(mi>gondolaSeq[i]){
      mi=gondolaSeq[i];
      id=i;
    }
    //mi=min(mi,gondolaSeq[i]);
    if(gondolaSeq[i]>n){
      gn.push_back(ii(gondolaSeq[i],-1));
    }
    else{
      nf[gondolaSeq[i]]=true;
    }
  }
  vector<int> go,gon(n,-1);
  if(mi>n){
    for(int i=0;i<n;i++){
      gon[i]=(i+1);
    }
  }
  else{
    int j=id;
    int aux=mi;
    while(true){
      if(j==gon.size()) j=0;
      if(gon[j]!=-1) break;
      gon[j]=aux;
      if(aux==n){
	aux=0;
      }
      aux++;
      j++;
    }
  }
  int j=0;
  for(int i=0;i<gon.size();i++){
    //     cout<<gon[i]<<" ";
    if(nf[gon[i]]==false){
      gn[j].second=gon[i];
      j++;
    }
  }
  // cout<<endl;
  int ga=n+1;
  j=0;
  int t=0;
  sort(gn.begin(),gn.end());
  /* for(int i=0;i<gn.size();i++){
    cout<<gn[i]<<" ";
  }
  cout<<endl;
  for(int i=0;i<go.size();i++){
    cout<<go[i]<<" ";
  }
  cout<<endl;*/
  for(int i=0;i<gn.size();i++){
    replacementSeq[j]=gn[i].second;
    j++;
    t++;
    while(true){
      if(ga==gn[i].first){
	ga++;
	break;
      }
      // ga++;
      replacementSeq[j]=ga;
      ga++;
      j++;
      t++;
    }
  }
  //cout<<t<<endl;
  return t;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  //cout<<"hi"<<endl;
  //cout<<valid(n,inputSeq)<<endl;
  if(valid(n,inputSeq)){
    vector<int> gn,dp;
    for(int i=0;i<n;i++){
      if(inputSeq[i]>n){
	gn.push_back(inputSeq[i]);
      }
    }
    long long r=1;
    for(int i=0;i<gn.size();i++){
      dp.push_back(gn[i]-n-1);
    }
    if(dp.size()==1) return 1;
    else{
      for(int i=0;i<dp.size();i++){
	//cout<<dp[i]<<" ";
	r*=(dp[i]%mod);
	r%=mod;
      }
     // cout<<endl;
      return r;
    }
    
  }
  else {return 0;}
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size()!=n) return 0;
        ~~~~~~~~^~~
gondola.cpp:40:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size()==n) return 1;
      ~~~~~~~~^~~
gondola.cpp:20:8: warning: unused variable 'sw' [-Wunused-variable]
   bool sw=0;
        ^~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j==gon.size()) j=0;
          ~^~~~~~~~~~~~
gondola.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gon.size();i++){
               ~^~~~~~~~~~~
gondola.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gn.size();i++){
               ~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:139:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gn.size();i++){
                 ~^~~~~~~~~~
gondola.cpp:144:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<dp.size();i++){
                   ~^~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:74:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if(j==gon.size()) j=0;
          ~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10