Submission #781942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781942	2023-07-13T14:02:01 Z	I_Love_EliskaM_	Gondola (IOI14_gondola)	C++14	Compilation error	0 ms	0 KB

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();
}

int countReplacement(int n, int a[]) {
  #define int ll
  set<int> s;
  forn(i,n) s.insert(a[i]);
  if (s.size()<n) 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 p=0;
    int k=n;
    for (int i=n+1; i<=v.back(); ++i) {
      if (v[p]==i) {
        --k; ++p; continue;
      }
      ans=(1ll*ans*k)%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 p=0;
  for (int i=n+1; i<=v.back(); ++i) {
    if (v[p]==i) {
      --k; ++p; continue;
    }
    ans=(1ll*ans*k)%mod;
  }
  return ans;
  #undef int
}

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

Compilation message

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];
      |   ^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:66:15: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if (s.size()<n) return 0;
      |               ^
gondola.cpp:69:25: error: no matching function for call to 'min(ll&, int&)'
   69 |   forn(i,n) m=min(m,a[i]);
      |                         ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from gondola.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
gondola.cpp:69:25: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |   forn(i,n) m=min(m,a[i]);
      |                         ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from gondola.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
gondola.cpp:69:25: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |   forn(i,n) m=min(m,a[i]);
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gondola.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
gondola.cpp:69:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |   forn(i,n) m=min(m,a[i]);
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from gondola.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
gondola.cpp:69:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |   forn(i,n) m=min(m,a[i]);
      |                         ^