제출 #12707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12707		qja0950	곤돌라 (IOI14_gondola)	C++98	55 / 100	32 ms	4620 KiB

gondola

#include "gondola.h"

#define MAX_N 101101
#define MAX_V 250052

int CheckV[MAX_V];

int valid(int n, int inputSeq[])
{
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        CheckV[now]++;
        if(CheckV[now] > 1) return 0;
    }
    
    int first = -1;
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    if(first == -1) return 1;
    
    
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (inputSeq[first] + i - 1) % n + 1;
        
        int now = inputSeq[index];
        if(now > n) continue;
        if(now != value) return 0;
    }
    return 1;
}

//----------------------
#include <algorithm>

using namespace std;

struct SORTR{
    int index;
    int value;
}SortR[MAX_N];
bool operator<(SORTR X, SORTR Y) {
    return X.value < Y.value;
}

int State[MAX_N];


int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int first = 0;
    for(int i=0; i<n; i++) {
        int now = gondolaSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (gondolaSeq[first] + i - 1) % n + 1;
        State[index] = value;
        
        SortR[i].index = i;
        SortR[i].value = gondolaSeq[i];
    }
    sort(SortR, SortR+n);
    
    int cnt = 0;
    int now = n;
    for(int i=0; i<n; i++) {
        int nowindex = SortR[i].index;
        int nowvalue = SortR[i].value;
        if(nowvalue < n) continue;
        while(State[nowindex] != nowvalue) {
            replacementSeq[cnt++] = State[nowindex];
            State[nowindex] = ++now;
        }
    }
    return cnt;
}

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

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