Submission #1027620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027620		MarwenElarbi	Gondola (IOI14_gondola)	C++17	65 / 100	65 ms	10348 KiB

gondola

    #include <bits/stdc++.h>
    #include "gondola.h"
    using namespace std;
    #define pb push_back
    #define se second
    #define fi first
    const int nax=5e5+5;
    const int MOD=1e9+9;
    int valid(int n, int inputSeq[])
    {
        vector<pair<int,int>> tab;
        bool test=true;
        set<int> stt;
        for (int i = 0; i < n; ++i)
        {
            stt.insert(inputSeq[i]);
        }
        test&=(stt.size()==n);
        int cnt=-1e9;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n){
                cnt=(inputSeq[i]-(i+1)+n)%n;
            }
        }
        if(cnt==-1e9) return test;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n){
                if((inputSeq[i]-(i+1)+n)%n!=cnt) test=false;
            }
        }
        return test;
    }
     
    //----------------------
     
    int replacement(int n, int gondolaSeq[], int replacementSeq[])
    {
        vector<pair<int,int>> tab;
        for (int i = 0; i < n; ++i)
        { 
            if(gondolaSeq[i]>n){
                tab.pb({gondolaSeq[i],i+1});
            }
        }
        sort(tab.begin(),tab.end());
        int cnt=n;
        int cur=0;
        for (int i = 0; i < tab.size(); ++i)
        {
            replacementSeq[cur++]=tab[i].se;
            cnt++;
            while(cnt<tab[i].fi){
                replacementSeq[cur++]=cnt++;
            }
        }
        return cur;   
    }
    
    //----------------------
    long long binpow(long long x,long long m){
        x%=MOD;
        long long res=1;
        while(m){
            if(m%2) res=res*x%MOD;
            x=x*x%MOD;
            m/=2;
        }
        return res;
    }
    int countReplacement(int n, int inputSeq[])
    {
        long long cur=1;
        set<int> st;
        if(!valid(n,inputSeq)) return 0;
        for (int i = 0; i < n; ++i)
        {
            st.insert(i);
        }
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]<=n) st.erase(inputSeq[i]);
        }
        if(st.size()==0) return 1;
        set<int> stt;
        for (int i = 0; i < n; ++i)
        {
            if(inputSeq[i]>n) stt.insert(inputSeq[i]);
        }
        int cnt=n;
        if(stt.size()==n) cur=n;
        while(stt.size()){
            //cout <<cnt<<endl;
            cur*=binpow(stt.size(),*stt.begin()-1-cnt)%MOD;
            cur%=MOD;
            cnt=*stt.begin();
            stt.erase(*stt.begin());
        }
        return cur;
    }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:18:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |         test&=(stt.size()==n);
      |                ~~~~~~~~~~^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 0; i < tab.size(); ++i)
      |                         ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |         if(stt.size()==n) cur=n;
      |            ~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 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