oj.uz

Submission #119636

# Submission time Handle Problem Language Result Execution time Memory
119636 2019-06-21T14:04:34 Z CaroLinda Gondola (IOI14_gondola) C++14
20 / 100
 62 ms 5112 KB 
#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;
const int maxn=1e5+10;

using namespace std ;

bool ok = false ;

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) {ok=true;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 ;
  }
  ok=true ;
  return 1 ;
}

int replacement(int n, int gondolaSeq[] , int replacementSeq[])
{
  if(!ok) return 0 ;
  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()){
      if(ind+n+1<=p[i].ff) { 
          replacementSeq[ind]=p[i].ss ;
          p[i].ss = ind+n+1 ;
          ind++ ;
      }
    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(!ok) return 0 ;
    int g ;
    for(g=0;g<n;g++)
    if(inputSeq[g]>n) break ;
    if(g==n+1) return 1 ;
    int k=-1 ;
    lp(i,0,n)
    if(inputSeq[i]<=n) k=i ;

    ll ans=1 ;
    int count=1;
    
    if(k == -1) {k=0 ; ans=n ; }
    else count=(inputSeq[k]-k-1)%n+1 ;
    
    vector<int> p ;
    
    p.pb(n+1) ;
    
    lp(i,0,n)
    if(inputSeq[i]>n)
    p.pb(inputSeq[i]) ;
    
    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

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:68:6:
   lp(i,0,p.size()){
      ~~~~~~~~~~~~               
gondola.cpp:68:3: note: in expansion of macro 'lp'
   lp(i,0,p.size()){
   ^~
gondola.cpp: In function 'int countReplacement(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:124:8:
     lp(i,1,p.size())
        ~~~~~~~~~~~~             
gondola.cpp:124:5: note: in expansion of macro 'lp'
     lp(i,1,p.size())
     ^~
gondola.cpp:109:9: warning: variable 'count' set but not used [-Wunused-but-set-variable]
     int count=1;
         ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 17 ms 2340 KB Output is correct
7 Correct 12 ms 1152 KB Output is correct
8 Correct 28 ms 4316 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 39 ms 4984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 14 ms 2424 KB Output is correct
7 Correct 11 ms 1152 KB Output is correct
8 Correct 30 ms 4348 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 39 ms 4988 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 21 ms 2304 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 62 ms 5112 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -