Submission #1146213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146213		julia_08	Gondola (IOI14_gondola)	C++20	35 / 100	9 ms	1500 KiB

gondola

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

using namespace std;

const int MAXN = 3e5 + 10;

int marc[MAXN], num[MAXN];

int id(int x, int n){
  if(x == -1) return n - 1;
  if(x == n) return 0;
  return x;
}

int valid(int n, int inputSeq[]){

  int pos_1 = -1;

  for(int i=0; i<n; i++){
    if(inputSeq[i] == 1) pos_1 = i;
    marc[inputSeq[i]] = 0;
  }

  for(int i=0; i<n; i++){
    marc[inputSeq[i]] ++;
    if(marc[inputSeq[i]] > 1) return 0;
  }

  int cur_pos = id(pos_1 + 1, n);

  while(cur_pos != pos_1){
    if(inputSeq[cur_pos] <= n && inputSeq[id(cur_pos - 1, n)] <= n && inputSeq[cur_pos] != inputSeq[id(cur_pos - 1, n)] + 1) return 0;
    cur_pos = id(cur_pos + 1, n);
  }

  return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){

  int pos = 1;

  for(int i=0; i<n; i++){
    if(gondolaSeq[i] <= n){
      pos = min(pos, i);
    }
  }

  num[pos] = gondolaSeq[pos];

  int cur_num = gondolaSeq[pos] - 1;

  int cur_pos = id(pos - 1, n);

  while(cur_num > 0){
    num[cur_pos] = cur_num;
    cur_num --; cur_pos = id(cur_pos - 1, n);
  }

  cur_num = gondolaSeq[pos] + 1;

  cur_pos = id(pos + 1, n);

  while(cur_num <= n){
    num[cur_pos] = cur_num;
    cur_num ++; cur_pos = id(cur_pos + 1, n);
  }

  vector<pair<int, int>> v;

  for(int i=0; i<n; i++){
    if(gondolaSeq[i] > n){
      v.push_back({gondolaSeq[i], num[i]});
    }
  }

  sort(v.begin(), v.end());

  int l = 0;

  int cur = n + 1;

  for(auto [x, i] : v){

    replacementSeq[l ++] = i;

    while(cur != x){
      replacementSeq[l ++] = cur;
      cur ++;
    }

    cur ++; // x nao quebra
  }

  // for(int i=0; i<l; i++) cout << replacementSeq[i] << " ";

  // cout << "\n";

  return l;
}

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