oj.uz

Submission #48767

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

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

#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 powr(int n,int k){
  if(k == 0)
    return 1;
  int hf = powr(n,k/2);
  hf = (1LL * hf * hf) % MOD;
  if(k&1)
    hf = (1LL * hf * n) % MOD;
  return hf;
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq)){
    return 0;
  }
  int ans = 1;
  int mn = (int)1e9 + 999;
  for(int i = 0;i < n;i ++)
    mn = min(mn,inputSeq[i]);
  if(mn > n)
    ans = n; // n cylcic rotations
  vector<int>nex;
  nex.push_back(n);
  for(int i = 0;i < n;i ++)
    if(inputSeq[i] > n)
      nex.push_back(inputSeq[i]);
  sort(nex.begin(),nex.end());
  int tk = (int)nex.size() - 1;
  for(int i = 1;i < (int)nex.size(); i ++){
    ans = (1LL * ans * powr(tk,nex[i] - nex[i - 1] - 1)) % MOD;
    --tk;
  }
  return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1816 KB Output is correct
2 Correct 4 ms 1836 KB Output is correct
3 Correct 3 ms 1840 KB Output is correct
4 Correct 3 ms 1880 KB Output is correct
5 Correct 2 ms 2012 KB Output is correct
6 Correct 8 ms 2440 KB Output is correct
7 Correct 26 ms 3056 KB Output is correct
8 Correct 13 ms 3684 KB Output is correct
9 Correct 10 ms 3684 KB Output is correct
10 Correct 16 ms 4360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4360 KB Output is correct
2 Correct 7 ms 4360 KB Output is correct
3 Correct 4 ms 4360 KB Output is correct
4 Correct 4 ms 4360 KB Output is correct
5 Correct 3 ms 4360 KB Output is correct
6 Correct 11 ms 4368 KB Output is correct
7 Correct 25 ms 4948 KB Output is correct
8 Correct 20 ms 5724 KB Output is correct
9 Correct 6 ms 5724 KB Output is correct
10 Correct 14 ms 6256 KB Output is correct
11 Correct 3 ms 6256 KB Output is correct
12 Correct 2 ms 6256 KB Output is correct
13 Correct 9 ms 6256 KB Output is correct
14 Correct 3 ms 6256 KB Output is correct
15 Correct 18 ms 6976 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6976 KB Output is correct
2 Correct 2 ms 6976 KB Output is correct
3 Correct 2 ms 6976 KB Output is correct
4 Correct 2 ms 6976 KB Output is correct
5 Correct 2 ms 6976 KB Output is correct
6 Correct 2 ms 6976 KB Output is correct
7 Correct 2 ms 6976 KB Output is correct
8 Correct 3 ms 6976 KB Output is correct
9 Correct 3 ms 6976 KB Output is correct
10 Correct 3 ms 6976 KB Output is correct
11 Correct 15 ms 6976 KB Output is correct
12 Correct 15 ms 7040 KB Output is correct
13 Correct 19 ms 8068 KB Output is correct
14 Correct 15 ms 8068 KB Output is correct
15 Correct 27 ms 9480 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9480 KB Output is correct
2 Correct 3 ms 9480 KB Output is correct
3 Correct 3 ms 9480 KB Output is correct
4 Correct 3 ms 9480 KB Output is correct
5 Correct 3 ms 9480 KB Output is correct
6 Correct 3 ms 9480 KB Output is correct
7 Correct 3 ms 9480 KB Output is correct
8 Correct 4 ms 9480 KB Output is correct
9 Correct 25 ms 10352 KB Output is correct
10 Correct 20 ms 10592 KB Output is correct
11 Correct 11 ms 10592 KB Output is correct
12 Correct 22 ms 10592 KB Output is correct
13 Correct 6 ms 10592 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10592 KB Output is correct
2 Correct 3 ms 10592 KB Output is correct
3 Correct 2 ms 10592 KB Output is correct
4 Correct 3 ms 10592 KB Output is correct
5 Correct 4 ms 10592 KB Output is correct
6 Correct 3 ms 10592 KB Output is correct
7 Correct 3 ms 10592 KB Output is correct
8 Correct 3 ms 10592 KB Output is correct
9 Correct 27 ms 11696 KB Output is correct
10 Correct 20 ms 12048 KB Output is correct
11 Correct 10 ms 12048 KB Output is correct
12 Correct 12 ms 12048 KB Output is correct
13 Correct 5 ms 12048 KB Output is correct
14 Runtime error 22 ms 14152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -