oj.uz

Submission #182543

# Submission time Handle Problem Language Result Execution time Memory
182543 2020-01-10T01:25:27 Z FieryPhoenix Gondola (IOI14_gondola) C++11
75 / 100
 122 ms 5252 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "gondola.h"
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000009
 
int valid(int N, int arr[]){
  set<int>st;
  int pos=-1;
  for (int i=0;i<N;i++){
    if (st.count(arr[i]))
      return 0;
    st.insert(arr[i]);
    if (arr[i]<=N)
      pos=i;
  }
  if (pos==-1)
    return 1;
  for (int i=0;i<N;i++){
    int j=(pos+i)%N;
    int target=arr[pos]+i;
    if (target>N)
      target-=N;
    if (arr[j]<=N && arr[j]!=target)
      return 0;
  }
  return 1;
}
 
 
bool used[250001];
int should[100001];
 
int replacement(int N, int g[], int repl[]){
  int nex=0;
  for (int i=0;i<N;i++){
    should[i]=i+1;
    nex=max(nex,g[i]);
  }
  int pos=-1;
  for (int i=0;i<N;i++)
    if (g[i]<=N)
      pos=i;
  for (int i=pos;i<pos+N;i++){
    int x=g[pos]+i-pos;
    if (x>N) x-=N;
    should[i%N]=x;
  }
  vector<int>v;
  for (int i=0;i<N;i++)
    used[g[i]]=true;
  priority_queue<pair<int,int>>pq;
  for (int i=0;i<N;i++)
    pq.push({g[i],i});
  while (!pq.empty()){
    int ind=pq.top().second;
    pq.pop();
    if (g[ind]<=N)
      continue;
    while (used[nex])
      nex--;
    if (nex<=N)
      nex=should[ind];
    v.push_back(nex);
    used[nex]=true;
    g[ind]=nex;
    pq.push({g[ind],ind});
  }
  reverse(v.begin(),v.end());
  for (int i=0;i<(int)v.size();i++)
    repl[i]=v[i];
  return (int)v.size();
}
 
int countReplacement(int n, int a[]){
  if (valid(n,a)==0)
    return 0;
  ll ans=1;
  vector<int>v;
  set<int>st;
  int mx=0;
  for (int i=0;i<n;i++)
    if (a[i]>n){
      mx=max(mx,a[i]);
      v.push_back(a[i]);
      st.insert(a[i]);
    }
  sort(v.begin(),v.end());
  for (int i=mx;i>n;i--){
    if (st.count(i))
      continue;
    int ind=upper_bound(v.begin(),v.end(),i)-v.begin();
    int num=(int)v.size()-ind;
    ans=(ans*max(1,num))%MOD;
  }
  int pos=-1;
  for (int i=0;i<n;i++)
    if (a[i]<=n)
      pos=i;
  if (pos==-1)
    for (int i=1;i<=n;i++)
      ans=(ans*i)%MOD;
  return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 20 ms 2552 KB Output is correct
7 Correct 13 ms 1144 KB Output is correct
8 Correct 35 ms 4344 KB Output is correct
9 Correct 12 ms 1656 KB Output is correct
10 Correct 49 ms 5112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 19 ms 2372 KB Output is correct
7 Correct 14 ms 1144 KB Output is correct
8 Correct 34 ms 4344 KB Output is correct
9 Correct 12 ms 1656 KB Output is correct
10 Correct 47 ms 4984 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 24 ms 2396 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 63 ms 5252 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 368 KB Output is correct
11 Correct 22 ms 2672 KB Output is correct
12 Correct 25 ms 2800 KB Output is correct
13 Correct 33 ms 2056 KB Output is correct
14 Correct 22 ms 2668 KB Output is correct
15 Correct 48 ms 2596 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 95 ms 4472 KB Output is correct
10 Correct 71 ms 3832 KB Output is correct
11 Correct 35 ms 1784 KB Output is correct
12 Correct 37 ms 1912 KB Output is correct
13 Incorrect 16 ms 760 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 122 ms 4600 KB Output is correct
10 Correct 81 ms 3832 KB Output is correct
11 Correct 36 ms 1856 KB Output is correct
12 Correct 36 ms 1912 KB Output is correct
13 Incorrect 15 ms 760 KB Output isn't correct
14 Halted 0 ms 0 KB -