oj.uz

Submission #70342

# Submission time Handle Problem Language Result Execution time Memory
70342 2018-08-22T16:32:52 Z alenam0161 Gondola (IOI14_gondola) C++17
60 / 100
 40 ms 2460 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int pos(int n,int rng[]){
    return min_element(rng,rng+n)-rng;
}
int ds(int p,int i,int n){
    return i<p ? n-p+i:i-p;
}
int valid(int n, int inputSeq[])
{
  int mn=pos(n,inputSeq);
  int mx=inputSeq[mn];
  int se=mn;
  if(distance(inputSeq,unique(inputSeq,inputSeq+n))!=n)return 0;
  for(int j=1;j<n;++j){
      mn++;
      if(mn==n)mn=0;
      if(inputSeq[mn]<=n&&inputSeq[mn]-inputSeq[se]!=ds(se,mn,n)){
          return 0;
      }
      if(inputSeq[mn]<=n)mx=max(mx,inputSeq[mn]);
  }
  return 1;
}

//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{

  vector<pair<int,int>> vx;
  int p=pos(n,gondolaSeq);
  if(gondolaSeq[p]<=n){
    if(p-(gondolaSeq[p]-1)<0){
        p-=(gondolaSeq[p]-1);
        p=n+p;
    }
    else{
        p-=(gondolaSeq[p]-1);
    }
  }
  for(int i=0;i<n;++i){
        vx.push_back({gondolaSeq[i],ds(p,i,n)});
  }
  sort(vx.begin(),vx.end());
  int sz=0;
  for(auto to:vx){
    int x=to.first;
    int st=to.second+1;
    if(st!=x){
        replacementSeq[sz++]=st;
        while(true){
            n++;
            st=n;
            if(st<x)
            replacementSeq[sz++]=n;
            else break;
        }
    }
  //  cout<<x<< " "<<st<<endl;
  }
  return sz;
}
//----------------------
const long long mod = 1e9+9;
long long pmod(int x,int y){
    if(y==1)return x;
    if(y==0)return 1;
    long long k=pmod(x,y/2);
 //   cout<<k<<endl;
    k*=k;
    k%=mod;
 //   cout<<k<<endl;
    if(y&1)k*=x;
    k%=mod;
  //  cout<<k<<endl;
    return k;
}
int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)return 0;
    int p=pos(n,inputSeq);
    bool ok=true;
    if(inputSeq[p]<=n){
        ok=false;
        if(p-(inputSeq[p]-1)<0){
            p-=(inputSeq[p]-1);
            p=n+p;
        }
        else{
            p-=(inputSeq[p]-1);
        }//To Do
    }
    vector<pair<int,int>> vx;
     for(int i=0;i<n;++i){
        vx.push_back({inputSeq[i],ds(p,i,n)});
      }
      sort(vx.begin(),vx.end());
      int sz=0;
    long long ans=1;
    int hw=n;
    int m=n;
    for(auto to:vx){
        int x=to.first;
        int st=to.second+1;
     //   cout<<ans<<endl;
        if(st!=x){
          //  cout<<n<<" "<<x<<" << "<<hw<<endl;
            ans*=max(1ll,pmod(x-n,hw-1));
            ans%=mod;
            n=x;
        }
        hw--;
      //  cout<<x<< " "<<st<<endl;
    }
    if(ok)ans*=m;
    ans%=mod;
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:99:11: warning: unused variable 'sz' [-Wunused-variable]
       int sz=0;
           ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 496 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 516 KB Output is correct
2 Correct 3 ms 548 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 8 ms 764 KB Output is correct
7 Correct 17 ms 928 KB Output is correct
8 Correct 13 ms 928 KB Output is correct
9 Correct 5 ms 928 KB Output is correct
10 Correct 13 ms 928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 928 KB Output is correct
2 Correct 2 ms 928 KB Output is correct
3 Correct 2 ms 928 KB Output is correct
4 Correct 2 ms 928 KB Output is correct
5 Correct 2 ms 928 KB Output is correct
6 Correct 6 ms 928 KB Output is correct
7 Correct 22 ms 928 KB Output is correct
8 Correct 13 ms 928 KB Output is correct
9 Correct 8 ms 928 KB Output is correct
10 Correct 13 ms 928 KB Output is correct
11 Correct 2 ms 928 KB Output is correct
12 Correct 2 ms 928 KB Output is correct
13 Correct 8 ms 928 KB Output is correct
14 Correct 2 ms 928 KB Output is correct
15 Correct 16 ms 928 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 928 KB Output is correct
2 Correct 3 ms 928 KB Output is correct
3 Correct 2 ms 928 KB Output is correct
4 Correct 2 ms 928 KB Output is correct
5 Correct 3 ms 928 KB Output is correct
6 Correct 2 ms 928 KB Output is correct
7 Correct 2 ms 928 KB Output is correct
8 Correct 2 ms 928 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 3 ms 928 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 928 KB Output is correct
2 Correct 2 ms 928 KB Output is correct
3 Correct 3 ms 928 KB Output is correct
4 Correct 3 ms 928 KB Output is correct
5 Correct 2 ms 928 KB Output is correct
6 Correct 3 ms 928 KB Output is correct
7 Correct 4 ms 928 KB Output is correct
8 Correct 3 ms 928 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 3 ms 928 KB Output is correct
11 Correct 26 ms 2084 KB Output is correct
12 Correct 26 ms 2084 KB Output is correct
13 Correct 18 ms 2084 KB Output is correct
14 Correct 17 ms 2084 KB Output is correct
15 Correct 40 ms 2460 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2460 KB Output is correct
2 Correct 3 ms 2460 KB Output is correct
3 Correct 2 ms 2460 KB Output is correct

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2460 KB Output is correct
2 Correct 3 ms 2460 KB Output is correct
3 Correct 2 ms 2460 KB Output is correct
4 Correct 3 ms 2460 KB Output is correct
5 Incorrect 2 ms 2460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2460 KB Output is correct
2 Correct 3 ms 2460 KB Output is correct
3 Correct 3 ms 2460 KB Output is correct
4 Correct 3 ms 2460 KB Output is correct
5 Incorrect 4 ms 2460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2460 KB Output is correct
2 Correct 3 ms 2460 KB Output is correct
3 Correct 3 ms 2460 KB Output is correct
4 Correct 2 ms 2460 KB Output is correct
5 Incorrect 2 ms 2460 KB Output isn't correct
6 Halted 0 ms 0 KB -