Submission #913214

#	Time	Username	Problem	Language	Result	Execution time	Memory
913214		12345678	Gondola (IOI14_gondola)	C++17	55 / 100	34 ms	5280 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[])
{
    set<int> st;
    for (int i=0; i<n; i++) 
    {
        if (st.find(inputSeq[i])!=st.end()) return 0;
        st.insert(inputSeq[i]);
    }
    int s, cnt(0);
    bool can=1;
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) mn=min(mn, {inputSeq[i], i});
    if (mn.first>n) return 1;
    cnt=mn.first;
    s=mn.second;
    for (int i=s; i<n; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    for (int i=0; i<s; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
    return can;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int cnt(0), res(0);
    set<pair<int, int>> s;
    for (int i=0; i<n; i++) if (gondolaSeq[i]>n) s.insert({gondolaSeq[i], i});
    pair<int, int> mn={INT_MAX, -1};
    for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) mn=min(mn, {gondolaSeq[i], i});
    if (mn.first==INT_MAX) mn={1, 0};
    cnt=mn.first-1;
    vector<int> p(n);
    //printf("%d\n", mn.second);
    for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
    //for (int i=0; i<n; i++) cout<<p[i]<<' ';
    //cout<<'\n';
    for (auto [x, y]:s)
    {
        //cout<<x<<' '<<y<<'\n';
        replacementSeq[res++]=p[y];
        while (res+n!=x) replacementSeq[res]=res+n, res++;
    }
    return res;
}

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

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

• 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