oj.uz

Submission #48770

# Submission time Handle Problem Language Result Execution time Memory
48770 2018-05-18T17:25:05 Z doowey Gondola (IOI14_gondola) C++14
60 / 100
 26 ms 2612 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 ll MOD = (int)1e9 + 9;

ll f;

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

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq)){
    return 0;
  }
  ll ans = 1;
  ll mz = (ll)1e8 + 99;
  for(int i = 0;i < n;i ++){
    mz = min(mz,(ll)inputSeq[i]);
  }
  if(mz > n)
    ans = n;
  vector<ll>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());
  ll 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:166: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 1384 KB Output is correct
3 Correct 4 ms 1420 KB Output is correct
4 Correct 3 ms 1472 KB Output is correct
5 Correct 3 ms 1524 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1524 KB Output is correct
2 Correct 3 ms 1572 KB Output is correct
3 Correct 3 ms 1572 KB Output is correct
4 Correct 3 ms 1572 KB Output is correct
5 Correct 3 ms 1572 KB Output is correct
6 Correct 8 ms 1724 KB Output is correct
7 Correct 25 ms 1856 KB Output is correct
8 Correct 16 ms 1980 KB Output is correct
9 Correct 8 ms 1980 KB Output is correct
10 Correct 16 ms 2108 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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