Submission #182555

#	Time	Username	Problem	Language	Result	Execution time	Memory
182555		FieryPhoenix	Gondola (IOI14_gondola)	C++11	90 / 100	1048 ms	4728 KiB

gondola

#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;
  int mx=0;
  for (int i=0;i<n;i++)
    if (a[i]>n){
      mx=max(mx,a[i]);
      v.push_back(a[i]);
    }
  sort(v.begin(),v.end());
  int ind=(int)v.size(),num=0;
  for (int i=mx;i>n;i--){
    while (ind>0 && i<=v[ind-1]){
      ind--;
      num++;
    }
    if (v[ind]==i)
      continue;
    ans=(ans*max(1,num));
    if (ans>MOD)
      ans%=MOD;
  }
  int pos=-1;
  for (int i=0;i<n;i++)
    if (a[i]<=n)
      pos=i;
  if (pos==-1)
    ans=(ans*n)%MOD;
  return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 0 / 10