Submission #582256

#	Time	Username	Problem	Language	Result	Execution time	Memory
582256		jasmin	Gondola (IOI14_gondola)	C++14	25 / 100	8 ms	980 KiB

gondola

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

const int inf=1e9;

vector<int> reorder(int n, int s[]){
    int small=inf; int ind=-1;
    for(int i=0; i<n; i++){
        if(s[i]<small){
            small=s[i];
            ind=i;
        }
    }

    if(n<small){
        vector<int> ans(n);
        for(int i=0; i<n; i++){
            ans[i]=s[i];
        }
        return ans;
    }
    int start=(n+ind-(small-1))%n;
    vector<int> ans(n);
    for(int i=0; i<n; i++){
        ans[i]=s[(start+i)%n];
    }
    return ans;
}

int valid(int n, int inputSeq[]){
    vector<int> s=reorder(n, inputSeq);
    set<int> used;
    for(int i=0; i<n; i++){
        if(s[i]!=i+1){
            if(s[i]<=n || used.find(s[i])!=used.end()){
                return false;
            }
            used.insert(s[i]);
        }
    }
    return true;
}

int maximum(vector<int>& s){
    int ans=-1;
    for(auto e: s){
        ans=max(ans, e);
    }
    return ans;
}

int replacement(int n, int gondolaSeq[], int ans[]){
    vector<int> s=reorder(n, gondolaSeq);
    int size=maximum(s)-n;

    set<int> usable;
    for(int i=0; i<n; i++){
        if(s[i]>n){
            ans[s[i]-n-1]=i;
            usable.insert(i);
        }
    }
    iota(s.begin(), s.end(), 1);
    for(int i=0; i<size; i++){
        if(ans[i]==-1){
            int ind=*usable.begin();
            ans[i]=s[ind];
            s[ind]=n+i+1;
            usable.erase(ind);
            usable.insert(i+n+1);
        }
        else{
            ans[i]=s[ans[i]];
            s[ans[i]]=n+i+1;
            usable.erase(s[ans[i]]);
        }
    }

    return size;
}

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

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int s[n];
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    cout << valid(n, s) << "\n";
    
    int rep[n*3];
    int size=replacement(n, s, rep);
    cout << size << "\n";
    for(auto e: rep){
        cout << e << " ";
    }
    cout << "\n";
}*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10