Submission #1153595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153595		zhasyn	Gondola (IOI14_gondola)	C++20	55 / 100	12 ms	2364 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 * 1e5 + 100, M = 1e7 + 10, len = 21, inf = 1e18;
const ll mod = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
bool cc[N];
int valid(int n, int arr[])
{
  int cur = 0;
  bool was = false;
  for(int i = 0; i < 2 * n; i++){
  	cur = cur%n + 1;
  	if(i < n){
	  	if(cc[arr[i%n]] == true) return 0;
	  	cc[arr[i%n]] = true;
  	}
  	if(was){
  		if(arr[i%n] > n) continue;
  		if(arr[i%n] != cur) return 0;
  	} else{
  		if(arr[i%n] <= n){
  			was = true;
  			cur = arr[i%n];
  		}
  	}
  }
  return 1;
}

//----------------------
int replacement(int n, int arr[], int res[])
{
  int cur = 0;
  bool was = false;
  vector <pii> vec;
  for(int i = 0; i < 2 * n; i++){
  	cur = cur%n + 1;
  	if(was == false && arr[i%n] <= n){
  		was = true;
  		cur = arr[i%n];
  	}
  	if(was == true){
  		if(cc[cur]) continue;
  		cc[cur] = true;
  		vec.pb({arr[i%n], cur});
  	}
  }
  if(was == false){
  	for(int i = 0; i < n; i++){
  		vec.pb({arr[i], i + 1});
  	}
  }
  sort(vec.begin(), vec.end());
  int from = 0, lt;
  bool mk = false;
  for(int i = 0; i < (int)vec.size(); i++){
  	if(vec[i].F == vec[i].S) continue;
  	res[from++] = vec[i].S;
  	if(mk == false) lt = n + 1;
  	else lt = vec[i - 1].F + 1;
  	//cout << vec[i].F << " "<< vec[i].S << " "<< lt << endl;
  	for(int j = lt; j < vec[i].F; j++){
  		res[from++] = j;
  	}
  	mk = true;
  }
  // for(int i = 0; i < from; i++){
  	// cout << res[i] << " ";
  // }
  // cout << endl;
  return from;
}

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

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