oj.uz

Submission #48771

# Submission time Handle Problem Language Result Execution time Memory
48771 2018-05-18T17:27:52 Z doowey Gondola (IOI14_gondola) C++14
60 / 100
 25 ms 2588 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

#define fi first
#define se second
#define mp make_pair

const int N = (int)25e4 + 1293;

int valid(int n, int inputSeq[])
{
  int cnt[N];
  for(int j = 0;j < N;j ++ )
    cnt[j] = 0;
  int rest[n];
  int maz = (int)4e5 + 12345;
  for(int i = 0; i < n;i ++){
    cnt[inputSeq[i]]++;
    if(cnt[inputSeq[i]] >= 2)
      return 0;
    maz = min(maz, inputSeq[i]);
    rest[i] = inputSeq[i];
  }
  if(maz > n)
    return 1;
  int p,j;
  for(int i = 0;i < n;i ++ ){
    if(rest[i] <= n){
      p = rest[i]+1;
      j = i+1;
      j %= N;
      while(p <= n){
        rest[j] = p;
        p++;
        j++;
        j%=n;
      }
      p = 1;
      while(p < rest[i]){
        rest[j] = p;
        j++;
        j %= n;
        p++;
      }
      break;
    }
  }
  for(int i = 0; i < n;i ++){
    if(inputSeq[i] <= n){
      if(rest[i] != inputSeq[i])
        return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int gondolas[], int replacementSeq[])
{
  int rx = 0;
  int start[n];
  bool is = false;
  for(int i = 0;i < n;i ++){
    if(gondolas[i] > n)
      is = true;
    if(gondolas[i] <= n)
      rx = i;
  }
  if(is == false)
    return 0;
  int ini;
  if(gondolas[rx] > n)
    start[rx] = 1;
  else
    start[rx] = gondolas[rx];
  int p = start[rx] + 1;
  ini = start[rx];
  rx ++ ;
  while(p <= n){
    rx %= n;
    start[rx] = p;
    rx++;
    p++;
  }
  p = 1;
  rx %= n;
  while(p < ini){
    start[rx] = p;
    p++;
    rx++;
    rx %= n;
  }
  vector<pii>qq;
  for(int i = 0;i < n;i ++){
    if(start[i] < gondolas[i]){
      qq.push_back(mp(gondolas[i],i));
    }
  }
  sort(qq.begin(),qq.end());
  int mak;
  int ii = n + 1;
  int ix;
  int sz = 0;
  for(auto x : qq){
    mak = x.fi;
    ix = x.se;
    replacementSeq[sz] = start[ix];
    sz++;
    start[ix] = ii;
    ii++;
    while(start[ix] < mak){
      replacementSeq[sz] = start[ix];
      start[ix] = ii;
      sz++;
      ii++;
    }
    ii = mak + 1;
  }
  return sz;
}

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

const int MOD = (int)1e9 + 9;

int f;

int powr(int n,int k){
  if(k == 0)
    return 1;
  f = powr(n,k/2);
  f = (1LL * f * f) % MOD;
  if(k & 1)
    f = (1LL * n * f) % MOD;
  return f;
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq)){
    return 0;
  }
  int ans = 1;
  int mz = (int)1e8 + 99;
  for(int i = 0;i < n;i ++){
    mz = min(mz,inputSeq[i]);
  }
  if(mz > n)
    ans = n;
  vector<int>gg;
  gg.push_back(n);
  for(int i = 0;i < n;i ++){
    if(inputSeq[i] > n)
      gg.push_back(inputSeq[i]);
  }
  sort(gg.begin(),gg.end());
  int left_over;
  left_over = (int)gg.size() - 1;
  for(int i = 1; i < gg.size(); i ++){
    ans *= powr(left_over,gg[i] - gg[i - 1] - 1);
    left_over -- ;
  }
  return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < gg.size(); i ++){
                  ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1620 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 9 ms 1764 KB Output is correct
7 Correct 15 ms 1892 KB Output is correct
8 Correct 14 ms 2040 KB Output is correct
9 Correct 6 ms 2040 KB Output is correct
10 Correct 13 ms 2156 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2588 KB Output is correct
2 Correct 4 ms 2588 KB Output is correct
3 Correct 3 ms 2588 KB Output is correct
4 Correct 4 ms 2588 KB Output is correct
5 Correct 4 ms 2588 KB Output is correct
6 Correct 3 ms 2588 KB Output is correct
7 Incorrect 3 ms 2588 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2588 KB Output is correct
2 Correct 4 ms 2588 KB Output is correct
3 Correct 3 ms 2588 KB Output is correct
4 Correct 3 ms 2588 KB Output is correct
5 Correct 3 ms 2588 KB Output is correct
6 Correct 2 ms 2588 KB Output is correct
7 Incorrect 4 ms 2588 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2588 KB Output is correct
2 Correct 3 ms 2588 KB Output is correct
3 Correct 3 ms 2588 KB Output is correct
4 Correct 3 ms 2588 KB Output is correct
5 Correct 3 ms 2588 KB Output is correct
6 Correct 3 ms 2588 KB Output is correct
7 Incorrect 3 ms 2588 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -