Submission #119645

#	Time	Username	Problem	Language	Result	Execution time	Memory
119645		CaroLinda	Gondola (IOI14_gondola)	C++14	100 / 100	87 ms	6008 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back

const int MOD=1e9+9;
const int maxn=1e5+10;

using namespace std ;

int valid(int n, int inputSeq[])
{
  set<int> s ;
  int k=-1 ;
  lp(i,0,n)
  {
    if( s.find(inputSeq[i]) != s.end() )
      return 0 ;
    s.insert(inputSeq[i]) ;
    if(inputSeq[i]<=n) k = i ;
  }
  if(k==-1) return 1 ;
  int count=(inputSeq[k]-k-1+n)%n+1 ;
  lp(i,0,n)
  {
    if(inputSeq[i]<=n && inputSeq[i]!=count)
      return 0 ;
    if (++count>n) count=1 ;
  }
  return 1 ;
}

int replacement(int n, int gondolaSeq[] , int replacementSeq[])
{
  
  int k=-1;
  lp(i,0,n)
  if(gondolaSeq[i]<=n)k=i ;

  int count ;

  if(k==-1)
    count=1 ;
  
  else count = (gondolaSeq[k]-k-1+n)%n+1 ;

  vector<pii> p ;

  lp(i,0,n)
  {
    if(gondolaSeq[i]>n)
    p.pb( pii( gondolaSeq[i] , count ) ) ;
    if(++count>n) count=1 ;
  }

  sort(p.begin(),p.end()) ;

  int ind=0 ;

  lp(i,0,p.size()){
    while(ind+n+1<=p[i].ff){
    replacementSeq[ind]=p[i].ss ;
    p[i].ss = ind+n+1 ;
    ind++ ;
    }
  }

  return ind ;

}

ll expo(ll x, int n)
{
    if(n==0) return 1 ;
    if(n==1) return x ;
    if(n%2==0)
    {
        ll aux=expo(x,n/2) ;
        return (aux*aux)%MOD ;
    }
    return (x*expo(x,n-1))%MOD ;
}

int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq)) return 0 ;
    int g ;
    for(g=0;g<n;g++)
    if(inputSeq[g]>n) break ;
    if(g==n+1) return 1 ;
    
    ll ans = 1 ;
    
    vector<int> p ;
    
    p.pb(n+1) ;
    
    lp(i,0,n)
    if(inputSeq[i]>n)
    p.pb(inputSeq[i]) ;

    if(p.size() == n+1 ) ans = n ;
    
    sort(p.begin(),p.end()) ;

    lp(i,1,p.size())
    {
        ans = (ans * expo(p.size() - i , p[i]-p[i-1] ) ) % MOD ;
        p[i] ++ ;
    }
    
    return ans ;
    
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
gondola.cpp:65:6:
   lp(i,0,p.size()){
      ~~~~~~~~~~~~               
gondola.cpp:65:3: note: in expansion of macro 'lp'
   lp(i,0,p.size()){
   ^~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p.size() == n+1 ) ans = n ;
        ~~~~~~~~~^~~~~~
gondola.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
gondola.cpp:111:8:
     lp(i,1,p.size())
        ~~~~~~~~~~~~             
gondola.cpp:111:5: note: in expansion of macro 'lp'
     lp(i,1,p.size())
     ^~

• 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: 10 / 10