Submission #781974

#	Time	Username	Problem	Language	Result	Execution time	Memory
781974		I_Love_EliskaM_	Gondola (IOI14_gondola)	C++14	100 / 100	32 ms	5216 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
const int inf=1e9;
const int mod=1e9+9;

int replacement(int n, int a[], int r[]) {
  int m=inf;
  forn(i,n) m=min(m,a[i]);
  if (m>n) {
    vector<int> p;
    set<int> s;
    forn(i,n) s.insert(i);
    map<int,int> mp;
    forn(i,n) mp[a[i]]=i;
    int l=0; forn(i,n) l=max(l,a[i]);
    vector<int> v(n); forn(i,n) v[i]=i+1;
    for (int i=n+1; i<=l; ++i) {
      if (mp.count(i)) {
        p.pb(v[mp[i]]);
        s.erase(mp[i]);
      } else {
        p.pb(v[*s.begin()]);
        v[*s.begin()]=i;
      }
    }
    forn(i,p.size()) r[i]=p[i];
    return p.size();
  }

  vector<int> p;
  set<int> s;
  forn(i,n) if (a[i]>n) s.insert(i);
  map<int,int> mp;
  forn(i,n) mp[a[i]]=i;
  int l=0; forn(i,n) l=max(l,a[i]);
  int z=-1;
  forn(i,n) if (a[i]<=n) z=i;
  vector<int> v(n); 
  if (z==-1) forn(i,n) v[i]=i+1;
  else forn(i,n) v[i]=((a[z]-1+i-z+n)%n)+1;
  for (int i=n+1; i<=l; ++i) {
    if (mp.count(i)) {
      p.pb(v[mp[i]]);
      s.erase(mp[i]);
    } else {
      p.pb(v[*s.begin()]);
      v[*s.begin()]=i;
    }
  }
  forn(i,p.size()) r[i]=p[i];
  return p.size();
}

ll pw(ll a, ll b) {
  ll r=1;
  while(b) {
    if (b&1) r=(1ll*r*a)%mod;
    a=(1ll*a*a)%mod;
    b>>=1;
  }
  return r;
}

int countReplacement(int n, int a[]) {
  vector<int> s; forn(i,n) s.pb(a[i]);
  sort(all(s));
  forn(i,n-1) if (s[i]==s[i+1]) return 0;

  int m=inf;
  forn(i,n) m=min(m,a[i]);
  if (m>n) {
    vector<int> v; forn(i,n) v.pb(a[i]);
    sort(all(v));
    ll ans=1;
    int k=n;
    int l=n;
    for(auto&x:v) {
      ans=(1ll*ans*pw(k,x-l-1))%mod;
      --k;
      l=x;
    }
    ans=(ans*n)%mod;
    return ans;
  }

  int i=0;
  for(;i<n;++i) if (a[i]<=n) break;
  i-=a[i]-1;
  if (i<0) i+=n;

  vector<int> v;

  int z=1;
  for (int j=i; j<i+n; ++j) {
    if (a[j%n]<=n) z&=a[j%n]==j-i+1;
    else v.pb(a[j%n]); 
  }
  if (!z) return 0;
  if (!v.size()) return 1;

  sort(all(v)); 
  int k=v.size();
  ll ans=1;
  int l=n;
  for(auto&x:v) {
    ans=(1ll*ans*pw(k,x-l-1))%mod;
    --k;
    l=x;
  }
  return ans;
}

int valid(int n, int a[]) {
  return !!countReplacement(n,a);
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   34 |     forn(i,p.size()) r[i]=p[i];
      |          ~~~~~~~~~~             
gondola.cpp:34:5: note: in expansion of macro 'forn'
   34 |     forn(i,p.size()) r[i]=p[i];
      |     ^~~~
gondola.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   58 |   forn(i,p.size()) r[i]=p[i];
      |        ~~~~~~~~~~               
gondola.cpp:58:3: note: in expansion of macro 'forn'
   58 |   forn(i,p.size()) r[i]=p[i];
      |   ^~~~

• 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: 10 / 10