Submission #734940

#	Time	Username	Problem	Language	Result	Execution time	Memory
734940		sandry24	Gondola (IOI14_gondola)	C++17	60 / 100	37 ms	4944 KiB

gondola

    #include <bits/stdc++.h>
    using namespace std;
     
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    typedef long long ll;
    typedef vector<int> vi;
    typedef pair<int, int> pi;
    #define pb push_back
    #define mp make_pair
    #define f first
    #define s second
     
     
    #include "gondola.h"
     
    map<int, int> freq;
     
    int valid(int n, int inputSeq[]){
        int index_under_n = -1;
        for(int i = 0; i < n; i++){
            freq[inputSeq[i]]++;
            if(freq[inputSeq[i]] > 1)
                return 0;
            if(inputSeq[i] <= n)
                index_under_n = i;
        }
        if(index_under_n == -1)
            return 1;
        int index = (index_under_n == n-1 ? 0 : index_under_n + 1);
        int next = (inputSeq[index_under_n] == n ? 1 : inputSeq[index_under_n] + 1);
        while(index != index_under_n){
            if(inputSeq[index] < n){
                if(inputSeq[index] != next){
                    return 0;
                }
            }
            index = (index == n-1 ? 0 : index + 1);
            next = (next == n ? 1 : next + 1);
        }
        return 1;
    }
     
    int replacement(int n, int gondolaSeq[], int replacementSeq[]){
        int index = -1, cnt = 0, next;
        for(int i = 0; i < n; i++)
            if(gondolaSeq[i] <= n)
                index = i;
        if(index == -1){
            index = 0;
            next = 1;
        } else next = gondolaSeq[index];
        vector<pi> temp;
        int current = n+1;
        while(cnt != n){
            if(gondolaSeq[index] != next)
                temp.pb({gondolaSeq[index], next});
            index = (index == n-1 ? 0 : index + 1);
            next = (next == n ? 1 : next + 1);
            cnt++;
        }
        sort(temp.begin(), temp.end());
        int ind = 0;
        for(int i = 0; i < temp.size(); i++){
            while(temp[i].f != temp[i].s){
                replacementSeq[ind] = temp[i].s;
                temp[i].s = current;
                current++;
                ind++;
            }
        }
        return ind;
    }
     
    ll bin_pow(ll a, ll b, ll mod){
        ll ans = 1;
        while(b > 0){
            if(b & 1)
                ans = ans * a % mod;
            a = a * a % mod;
            b /= 2;
        }
        return ans;
    }
     
    int countReplacement(int n, int inputSeq[]){
        if(!valid(n, inputSeq))
            return 0;
        return 1;
    }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i = 0; i < temp.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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10