Submission #1143743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143743		Matbubble	Gondola (IOI14_gondola)	C++20	20 / 100	1093 ms	4420 KiB

gondola

#include "gondola.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
using namespace std;

int valid(int n, int inputSeq[])
{
  vector<int>extra;
  set<int>freq;
  for(int i=0 ; i<n ; i++){
    int curr=inputSeq[i], next=inputSeq[(i+1)%n];
    if(freq.count(curr)) return 0;
    freq.insert(curr);
    if(curr>n) extra.push_back(curr);
    if(next>n || curr>n) continue;
    if((next-curr+n)%n>1) return 0;
  }
  sort(extra.begin(), extra.end());
  for(int i=0 ; i<(int)extra.size()-1 ; i++){
    if(extra[i+1]-extra[i]>1) return 0;
  }
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  using T=pair<int, int>;
  vector<T>extra;
  int posi=-1;
  for(int i=0 ; i<n ; i++){
    if(gondolaSeq[i]<=n){
      posi=i;
      break;
    }
  }
  if(posi>=0){
    vector<int>nuevo(n+1);
    nuevo[posi]=gondolaSeq[posi];
    int curr=(posi+1)%n;
    while(curr!=posi){
      int last=(curr-1+n)%n;
      nuevo[curr]=nuevo[last]+1;
    }
    for(int i=0 ; i<n ; i++){
      if(gondolaSeq[i]>n) extra.push_back({nuevo[i], gondolaSeq[i]});
    }
  }else{
    for(int i=0 ; i<n ; i++){
      extra.push_back({i+1, gondolaSeq[i]});
    }
  }
  sort(extra.begin(), extra.end(), [](T a, T b){
    return a.second<b.second;
  });
  int actual=n+1; posi=0;
  for(int i=0 ; i<(int)extra.size() ; i++){
    while(extra[i].first!=extra[i].second){
      // dbg(123)
      replacementSeq[posi]=extra[i].first;
      posi++;
      extra[i].first=actual;
      actual++;
    }
  }
  return posi;
}

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

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 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