Submission #432949

#	Time	Username	Problem	Language	Result	Execution time	Memory
432949		REALITYNB	Gondola (IOI14_gondola)	C++17	70 / 100	305 ms	262148 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 3e5+1 ;
int b[N];
int valid(int n ,int* a){
    set<int> el ;
    for(int i=0;i<n;i++) el.insert(a[i]) ;
    if(el.size()!=n) return 0 ;
    bool flg= 0 ;
    for(int i=0;i<n;i++){
        if(a[i]>n) continue;
        for(int j=i;j<=n+i;j++){
            if(a[j%n]>n) {b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
                continue ;
            }
            if(a[j%n]==((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n)){
                    b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
                    continue ;
            }
            return 0;
        }
        break ;
    }
    return 1 ;
}
int replacement(int n , int* a , int* ans){
    valid(n,a) ;
    vector<int> hey ;
    for(int i=0;i<n;i++)if(a[i]>n) hey.push_back(i) ;
    if(hey.size()==n){
        for(int i=0;i<2e9;i++) hey.push_back(0) ;
        return 1 ;
    }
    //for(int i=0;i<n;i++) cout << b[i] << " ";
   // cout << endl ;
    sort(hey.begin(),hey.end(),[&](int i ,int j){
        return a[i]>a[j] ;
    }) ;
    int res = 0 ;
    int mx = 0 ;
    for(int i=0;i<n;i++) mx = max(mx,a[i]) ;
   // cout << mx << endl ;
   // for(int x: hey) cout << x << " ";
    //cout << endl ;
    for(int i=n+1;i<=mx;i++){
        if(a[hey.back()]<i){
            hey.pop_back();
        }
        ans[res++]=b[hey.back()];
        b[hey.back()]=i;
    }
    return res;
}
int countReplacement(int n,int* a){
    const int md = 1e9+9 ;
    if(valid(n,a)==0) return 0 ;
    #define int long long
    int spots = 0 ;
    for(int i=0;i<n;i++) spots+=(a[i]>n) ;
    int ans = (spots==n?n:1), mx =  0 ;
    for(int i=0;i<n;i++) mx = max(mx,(int)a[i]) ;
    set<int> vis ;
    for(int i=0;i<n;i++) if(a[i]>n)vis.insert(a[i]) ;
    int last = n;
    function<int(int,int)> be=[](int b ,int e){
        int ans =1;
        while(e){
            if(e&1) ans*=b;
            b*=b,e/=2;
            ans%=md,b%=md ;
        }
        return ans;
    } ;
    //cout << ans << ndl ;
    for(int x: vis)
        (ans*=be(spots,(x-last-1)))%=md,--spots,last = x  ;
       // cout << last << " " << x << " " <<spots << " " << be(spots,(x-last-1)) << endl ;


    #undef int
    int hey = ans ;
    return hey;
}
/*int main(){
    int a[7] = {2, 3, 4, 9, 6, 7, 1} ;
    int ans[10] ;
    int n = replacement(7,a,ans);
    cout << n <<endl ;
    for(int i=0;i<n;i++) cout << ans[i] << " " ;
    return 0 ;
}
*/

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:9:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |     if(el.size()!=n) return 0 ;
      |        ~~~~~~~~~^~~
gondola.cpp:10:10: warning: unused variable 'flg' [-Wunused-variable]
   10 |     bool flg= 0 ;
      |          ^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:31:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     if(hey.size()==n){
      |        ~~~~~~~~~~^~~

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