Submission #787794

#	Time	Username	Problem	Language	Result	Execution time	Memory
787794		tolbi	Gondola (IOI14_gondola)	C++17	100 / 100	51 ms	6012 KiB

gondola

    #pragma optimize("Bismillahirrahmanirrahim")
    //█▀█─█──█──█▀█─█─█
    //█▄█─█──█──█▄█─█■█
    //█─█─█▄─█▄─█─█─█─█
    //Allahuekber
    //ahmet23 orz...
    //FatihSultanMehmedHan
    //YavuzSultanSelimHan
    //AbdulhamidHan
    //Sani buyuk Osman Pasa Plevneden cikmam diyor
    #define author tolbi
    #include <bits/stdc++.h>
    using namespace std;
    template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
    template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it<<" ";return os;}
    template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it<<" ";return os;}
    ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
    #define endl '\n'
    #define deci(x) int x;cin>>x;
    #define decstr(x) string x;cin>>x;
    #define cinarr(x) for(auto &it : x) cin>>it;
    #define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
    #define sortarr(x) sort(x.begin(), x.end())
    #define sortrarr(x) sort(x.rbegin(), x.rend())
    #define rev(x) reverse(x.begin(), x.end())
    #define tol(bi) (1ll<<((int)(bi)))
    typedef long long ll;
    const ll INF = LONG_LONG_MAX;
    const ll MOD = 1e9+9;
    mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
     
    #include "gondola.h"
     
    int valid(int n, int inputSeq[])
    {
        map<int,bool> mp;
        int pos = -1;
        for (int i = 0; i < n; ++i)
        {
            if (mp[inputSeq[i]]) return 0;
            mp[inputSeq[i]]=true;
        }
        for (int i = 0; i < n; ++i)
        {
            if (inputSeq[i]<=n){
                pos=i;
                break;
            }
        }
        if (pos==-1) return 1;
        pos-=inputSeq[pos]-1;
        if (pos<0) pos+=n;
        for (int i = 0; i < n; i++){
            int pp = (pos+i)%n;
            if (inputSeq[pp]>n) continue;
            if (inputSeq[pp]!=i+1) return 0;
        }
        return 1;
    }
     
    //----------------------
     
    int replacement(int n, int gondolaSeq[], int replacementSeq[])
    {
        vector<int> arr(n);
        int start = 0;
        vector<pair<int,int>> gerek;
        for (int i = 0; i < n; ++i)
        {
            if (gondolaSeq[i]<=n) continue;
            gerek.push_back({gondolaSeq[i],i});
        }
        for (int i = 0; i < n; i++){
            if (gondolaSeq[i]<=n){
                start=i-gondolaSeq[i]+1;
                break;
            }
        }
        if (start<n) start+=n;
        for (int i = 0; i < n; i++){
            int ppos = (start+i)%n;
            arr[ppos]=i+1;
        }
        int crr = n+1;
        int res = 0;
        sortarr(gerek);
        for (int i = 0; i < gerek.size(); ++i)
        {
            int hedef = gerek[i].first;
            int node = gerek[i].second;
            while (arr[node]<hedef){
                replacementSeq[res]=arr[node];
                arr[node]=crr;
                crr++,res++;
            }
        }
        return res;
    }
     
    //----------------------
    ll fpow(ll base, ll pow){
        ll res = 1;
        base%=MOD;
        while (pow>0){
            if (pow&1){
                res*=base;
                res%=MOD;
            }
            base*=base;
            base%=MOD;
            pow>>=1;
        }
        return res;
    }
    int countReplacement(int n, int inputSeq[])
    {
        if (!valid(n,inputSeq)) return 0;
        vector<ll> kk;
        bool boolean=true;
        for (int i = 0; i < n; i++){
            if (inputSeq[i]>n) kk.push_back(inputSeq[i]);
            else boolean=false;
        }
        sortarr(kk);
        ll ans = 1;
        if (boolean) ans=n;
        ll lel = n+1;
        for (int i = 0; i < kk.size(); i++){
            ans*=fpow((ll)kk.size()-i,kk[i]-lel);
            ans%=MOD;
            lel=kk[i]+1;
        }
        return ans;
    }

Compilation message (stderr)

gondola.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 |     #pragma optimize("Bismillahirrahmanirrahim")
      | 
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:87: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]
   87 |         for (int i = 0; i < gerek.size(); ++i)
      |                         ~~^~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for (int i = 0; i < kk.size(); 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