Submission #434296

#	Time	Username	Problem	Language	Result	Execution time	Memory
434296		illyakr	Gondola (IOI14_gondola)	C++14	75 / 100	31 ms	2452 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define ll long long

bool used[301010];
int valid(int n, int inputSeq[]) {
    int mn = 1010101010, sv = -1;
    for (int i = 0; i < n; i++) {
        if (used[inputSeq[i]])return 0;
        used[inputSeq[i]] = true;
        if (mn > inputSeq[i]) {
            mn = inputSeq[i];
            sv = i;
        }
    }
    if (mn > n)return 1;
    int go = mn;
    for (int i = sv - 1; i >= 0; i--) {
        go--;
        if (go < 1)go += n;
        if (inputSeq[i] > n)continue;
        if (inputSeq[i] != go)return 0;
    }
    for (int i = n - 1; i > sv; i--) {
        go--;
        if (go < 1)go += n;
        if (inputSeq[i] > n)continue;
        if (inputSeq[i] != go)return 0;
    }


    return 1;
}

//----------------------

int put[301010];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int mn = 1010101010, sv = -1;
    for (int i = 0; i < n; i++) {
        if (mn > gondolaSeq[i]) {
            mn = gondolaSeq[i];
            sv = i;
        }
    }
    int mx = 0;
    for (int i = 0; i < n; i++)mx = max(mx, gondolaSeq[i]);

    if (mn > n) {
        vector<int> use;
        for (int i = n + 1; i <= mx; i++)
            use.push_back(i);
        reverse(use.begin(), use.end());

        vector<pair<int, int> > sv;
        for (int i = 0; i < n; i++)
            sv.push_back({gondolaSeq[i], i});
        sort(sv.begin(), sv.end(), [](pair<int, int> q, pair<int, int> w) {
             return q.first < w.first;
        });

        int sz = 0;
        for (int i = 0; i < n; i++) {
            replacementSeq[sz++] = sv[i].second + 1;
            int el = use[use.size() - 1];
            use.pop_back();
            while (!use.empty() && el != sv[i].first) {
                replacementSeq[sz++] = el;
                el = use[use.size() - 1];
                use.pop_back();
            }
        }
        return sz;
    }
    vector<int> use;
    for (int i = n + 1; i <= mx; i++)
        use.push_back(i);
    reverse(use.begin(), use.end());

    vector<pair<int, int> > SV;

    int go = mn;
    for (int i = sv - 1; i >= 0; i--) {
        go--;
        if (go < 1)go += n;
        if (gondolaSeq[i] > n){SV.push_back({gondolaSeq[i], go});continue;}
    }
    for (int i = n - 1; i > sv; i--) {
        go--;
        if (go < 1)go += n;
        if (gondolaSeq[i] > n){SV.push_back({gondolaSeq[i], go});continue;}
    }

    sort(SV.begin(), SV.end(), [](pair<int, int> q, pair<int, int> w) {
         return q.first < w.first;
    });
//    for (auto [first, second] : SV) {
//        cout << first << " " << second << " << " << endl;
//    }
    int sz = 0;
    for (auto [first, second] : SV) {
        replacementSeq[sz++] = second;
        int el = use[use.size() - 1];
        use.pop_back();
        while (!use.empty() && el != first) {
            replacementSeq[sz++] = el;
            el = use[use.size() - 1];
            use.pop_back();
        }
    }
    return sz;
}

//----------------------
const ll mod = 1000000009;

ll bp(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)res *= a;
        a *= a;
        b /= 2;

        res %= mod;
        a %= mod;
    }
    return res;
}
ll ans = 1;
int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq))return 0;
    ll mn = 1010101010, sv = -1;
    for (ll i = 0; i < n; i++) {
        if (mn > inputSeq[i]) {
            mn = inputSeq[i];
            sv = i;
        }
    }
    if (mn <= n) {
        vector<ll> can = {0};
        for (ll i = 0; i < n; i++) {
            if (inputSeq[i] > n)
                can.push_back(inputSeq[i] - n);
        }
        sort(can.begin(), can.end());
        for (ll i = 1; i < can.size(); i++) {
            ans *= bp((ll)(can.size() - i), (ll)(can[i] - can[i - 1] - 1));
            ans %= mod;
        }
        return ans;
    } else {
        vector<ll> can = {0};
        for (ll i = 0; i < n; i++) {
            if (inputSeq[i] > n)
                can.push_back(inputSeq[i] - n);
        }
        sort(can.begin(), can.end());
        for (ll i = 1; i < can.size(); i++) {
            ans *= bp((ll)(can.size() - i), (ll)(can[i] - can[i - 1] - 1));
            ans %= mod;
        }
        return ans*n;
    }
}

/**
*/

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:102:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |     for (auto [first, second] : SV) {
      |               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:147:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (ll i = 1; i < can.size(); i++) {
      |                        ~~^~~~~~~~~~~~
gondola.cpp:159:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for (ll i = 1; i < can.size(); i++) {
      |                        ~~^~~~~~~~~~~~
gondola.cpp:133:25: warning: variable 'sv' set but not used [-Wunused-but-set-variable]
  133 |     ll mn = 1010101010, sv = -1;
      |                         ^~

• 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: 0 / 15
• Subtask 10: 0 / 10