Submission #235807

#	Time	Username	Problem	Language	Result	Execution time	Memory
235807		DanerZein	Gondola (IOI14_gondola)	C++14	90 / 100	1094 ms	5752 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){
    //  cout<<"hi"<<endl;
    int j=id;
    int aux=mi;
    while(true){
      if(vis[j]!=0) break;
      if(j==n) j=0;
      if(aux==n+1) aux=1;
      if(inputSeq[j]<=n){
	//	cout<<inputSeq[j]<<" "<<aux<<" "<<j<<endl;
	if(inputSeq[j]!=aux) return 0;
      }
      vis[j]=1;
      j++;
      aux++;
    }
    //cout<<"1"<<endl;
    if(s.size()!=n) return 0;
    return 1;
  }
  if(s.size()!=n) return 0;
  else return 1;
}

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

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<long long>gn;
    for(int i=0;i<n;i++){
      if(inputSeq[i]>n){
	gn.push_back(inputSeq[i]);
      }
    }
    long long gr=n+1;
    long long j=0;
    long long r=1;
    if(gn.size()==n) r=n;
    sort(gn.begin(),gn.end());
    while(true){
      //    cout<<j<<" "<<gn.size()<<" "<<gr<<endl;
      if(j==gn.size()) break;
      if(gr==gn[j]){
	gr++;
	j++;
	continue;
      }
      r=(r%mod*(gn.size()-j)%mod)%mod;
      gr++;
    }
    return r;
  }
  else {
    return 0;}
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size()!=n) return 0;
        ~~~~~~~~^~~
gondola.cpp:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size()!=n) return 0;
      ~~~~~~~~^~~
gondola.cpp:20:8: warning: unused variable 'sw' [-Wunused-variable]
   bool sw=0;
        ^~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:77:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j==gon.size()) j=0;
          ~^~~~~~~~~~~~
gondola.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gon.size();i++){
               ~^~~~~~~~~~~
gondola.cpp:108: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:144:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(gn.size()==n) r=n;
        ~~~~~~~~~^~~
gondola.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j==gn.size()) break;
          ~^~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:77:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if(j==gon.size()) j=0;
          ~^~~~~~~~~~~~

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