Submission #27749

#	Time	Username	Problem	Language	Result	Execution time	Memory
27749		zoomswk	Gondola (IOI14_gondola)	C++14	55 / 100	56 ms	7484 KiB

gondola

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

map<int, int> occ;

int valid(int n, int inputSeq[]){
    for(int i=0; i<n; i++){
        inputSeq[i]--;
        if(occ[inputSeq[i]]) return 0;
        occ[inputSeq[i]] = 1;
    }
    int must = -1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n) must = i;
    if(must == -1) return 1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n && (inputSeq[i]+n+must-i)%n != inputSeq[must]) return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int inputSeq[100005];
    for(int i=0; i<n; i++) gondolaSeq[i]--;
    int must = -1;
    for(int i=0; i<n; i++) if(gondolaSeq[i] < n) must = i;
    if(must == -1){
        for(int i=0; i<n; i++) inputSeq[i] = i;;
    } else{
        int cur = gondolaSeq[must];
        for(int i=must-1; i>=0; i--){
            cur--;
            if(cur < 0) cur += n;
            inputSeq[i] = cur;
        }
        cur = gondolaSeq[must];
        for(int i=must+1; i<n; i++){
            cur++;
            if(cur >= n) cur -= n;
            inputSeq[i] = cur;
        }
    }
    priority_queue<pair<int, int>> pq;
    for(int i=0; i<n; i++) if(gondolaSeq[i] >= n) pq.push({-gondolaSeq[i], i});
    int ptr = n-1;
    int sz = 0;
    while(!pq.empty()){
        int num = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        while(ptr < num){
            replacementSeq[sz++] = inputSeq[pos]+1;
            inputSeq[pos] = ++ptr;
        }
    }
    return sz;
}

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

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