Submission #819940

#	Time	Username	Problem	Language	Result	Execution time	Memory
819940		Cyber_Wolf	Gondola (IOI14_gondola)	C++17	30 / 100	7 ms	1132 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg MOD = 1e9+9;

int valid(int n, int v[])
{
	int idx = 0;
	for(int i = 0; i < n; i++)
	{
		if(v[i] == 1)	idx = i;
	}
	int x = n, b = 1, val = 1;
	while(x--)
	{
		b &= (v[idx] == val);
		idx = (idx+1)%n;
		val++;
	}
	return b;
}


int replacement(int n, int v[], int r[])
{
	int o = 0;
	multiset<lg> mst, not_taken;
	for(int i = 0; i < n; i++)	
	{
		mst.insert(v[i]);
	}
	for(int i = 1; i <= *(--mst.end()); i++)
	{
		if(mst.find(i) == mst.end())	not_taken.insert(i);
	}
	while(not_taken.size())
	{
		int val = *(--mst.end());
		mst.erase(--mst.end());
		mst.insert(*(--not_taken.end()));
		r[o++] = *(--not_taken.end());
		not_taken.erase(--not_taken.end());
	}
	reverse(r, r+o);
	return o;
}

lg fast_power(lg n, lg k)
{
	lg ans = 1;
	while(k)
	{
		if(k&1)	ans = (ans*n)%MOD;
		n = (n*n)%MOD;
		k >>= 1;
	}
	return ans;
}

int countReplacement(int n, int in[])
{
	int mxm = 0, un = 0;
	set<lg> se;
	for(int i = 0; i < n; i++)
	{
		mxm = max(mxm, in[i]);
		un += (in[i] > n);
		se.insert(in[i]);
	}
	if(se.size() < n)	return 0;
	int ans = 1;
	for(int i = 1; i <= mxm-n-un; i++)	ans = (ans*i)%MOD;
	for(int i = 1; i < mxm-n; i++)	ans = (ans*i)%MOD;
	for(int i = 1; i < un; i++)	ans = (ans*fast_power(i, MOD-2))%MOD;
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:48:7: warning: unused variable 'val' [-Wunused-variable]
   48 |   int val = *(--mst.end());
      |       ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:80:15: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  if(se.size() < n) return 0;
      |     ~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 5 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10