oj.uz

Submission #48769

# Submission time Handle Problem Language Result Execution time Memory
48769 2018-05-18T17:19:51 Z doowey Gondola (IOI14_gondola) C++14
60 / 100
 25 ms 2512 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 powr(ll n,int k){
  if(k == 0)
    return 1LL;
  ll p = 1;
  ll sk = n;
  ll ans = 1;
  while(p <= k){
    if(k & p){
      ans *= sk;
      ans %= MOD;
    }
    sk *= sk;
    sk %= MOD;
    p *= 2;
  }
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq)){
    return 0;
  }
  ll 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());
  ll tk = (ll)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;
}

Compilation message

gondola.cpp: In function 'll powr(ll, int)':
gondola.cpp:146:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1512 KB Output is correct
2 Correct 3 ms 1512 KB Output is correct
3 Correct 3 ms 1512 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 3 ms 1512 KB Output is correct
6 Correct 13 ms 1736 KB Output is correct
7 Correct 15 ms 2000 KB Output is correct
8 Correct 14 ms 2132 KB Output is correct
9 Correct 6 ms 2132 KB Output is correct
10 Correct 25 ms 2132 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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