oj.uz

Submission #70343

# Submission time Handle Problem Language Result Execution time Memory
70343 2018-08-22T16:34:27 Z alenam0161 Gondola (IOI14_gondola) C++17
60 / 100
 27 ms 2600 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(long long x,long long 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;
    long long hw=n;
    long long 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;
            long long e=x-n;
            ans*=max(1ll,pmod(e,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 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 700 KB Output is correct
3 Correct 3 ms 700 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 9 ms 720 KB Output is correct
7 Correct 16 ms 848 KB Output is correct
8 Correct 13 ms 848 KB Output is correct
9 Correct 8 ms 848 KB Output is correct
10 Correct 16 ms 848 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 892 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Correct 2 ms 892 KB Output is correct
4 Correct 2 ms 892 KB Output is correct
5 Correct 2 ms 892 KB Output is correct
6 Correct 3 ms 892 KB Output is correct
7 Correct 3 ms 892 KB Output is correct
8 Correct 2 ms 892 KB Output is correct
9 Correct 4 ms 892 KB Output is correct
10 Correct 3 ms 892 KB Output is correct
11 Correct 20 ms 2100 KB Output is correct
12 Correct 21 ms 2100 KB Output is correct
13 Correct 22 ms 2100 KB Output is correct
14 Correct 26 ms 2100 KB Output is correct
15 Correct 27 ms 2600 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2600 KB Output is correct
2 Correct 3 ms 2600 KB Output is correct
3 Correct 3 ms 2600 KB Output is correct
4 Correct 3 ms 2600 KB Output is correct
5 Incorrect 3 ms 2600 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 2600 KB Output is correct
2 Correct 2 ms 2600 KB Output is correct
3 Correct 3 ms 2600 KB Output is correct
4 Correct 2 ms 2600 KB Output is correct
5 Incorrect 2 ms 2600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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