Submission #434207

#	Time	Username	Problem	Language	Result	Execution time	Memory
434207		illyakr	Gondola (IOI14_gondola)	C++14	55 / 100	25 ms	2592 KiB

gondola

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

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;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

/**
4
6
9 6 11 8 3 4


4
4
4 5 6 7

4
4
7 9 5 8

4
6
9 8 10 13 12 11
*/

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [first, second] : SV) {
      |               ^

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