Submission #1263359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263359		DeltaStruct	Gondola (IOI14_gondola)	C++20	20 / 100	13 ms	1864 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

int valid(int n,int A[]){
  for (int i(0);i < n;++i) --A[i];
  set<int> S; for (int i(0);i < n;++i) if (A[i]<n) S.emplace((A[i]+n-i)%n);
  return (int)(S.size()<=1);
}

int replacement(int n,int A[],int B[]){
  int m = *max_element(A,A+n); sort(A,A+n); for (int i(0);i < n;++i) --A[i];
  multiset<int> S;
  for (int i(0);i < n;++i) if (!binary_search(A,A+n,i)) S.emplace(i+1);
  for (int i(n);i < m;++i){
    B[i-n] = *S.begin(),S.erase(S.begin());
    if (!binary_search(A,A+n,i)) S.emplace(i+1);
  }
  return m-n;
}

int countReplacement(int n,int A[]){
  if (!valid(n,A)) return 0;
  sort(A,A+n); long long mod = 1000000007; for (int i(0);i < n;++i) --A[i];
  auto modpow = [&mod](long long x,int i) -> int {
    long long ret = 1;
    while(i){
      if (i&1) (ret *= x) %= mod;
      (x *= x) %= mod,i>>=1;
    }
    return ret;
  };
  int m = A+n-lower_bound(A,A+n,n); long long ret = 1;
  for (int i(0),p(n);i < m;p=A[n-m+i++]){
    (ret *= modpow(m-i,A[n-m+i]-p+1)) %= mod;
  }
  return ret;
}

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