Submission #131380

#	Time	Username	Problem	Language	Result	Execution time	Memory
131380		MAMBA	Gondola (IOI14_gondola)	C++17	100 / 100	77 ms	6024 KiB

gondola

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

using namespace std;

#define rep(i, j , k) for(int i = j; i < (int) k; i++)

typedef vector<int> vi;

const int N = 3e5 + 10;

int pos[N];

map<int , int> mp;

int valid(int n, int A[])
{
	mp.clear();
	rep(i , 0 , n) {
		if (mp.count(A[i])) return 0;
		mp[A[i]] = i;
	}

	int last = -1;
	rep(i , 1 , n + 1) 
		if(mp.count(i)) {
			if (!~last) {
				last = i;
				continue;
			}
			if ((i - last) != (mp[i] - mp[last] + n) % n)
				return 0;
		}
	return 1;
}

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

int lo[N];
set<int> st;

int replacement(int n, int A[], int B[])
{
	st.clear();
	memset(pos , -1, sizeof(pos));
	int mx = -1;
	rep(i , 0 , n) {
		pos[A[i]] = i;
		mx = max(mx , A[i]);
	}

	bool flag = false;
	rep(i , 1 , n + 1) 
		if (~pos[i]) {
			rep(j , 1 , n + 1) {
				lo[(pos[i] + j - i + n) % n] = j;
				if(!~pos[j])
					st.insert((pos[i] + j - i + n) % n);
			}
			flag = true;
			break;
		}
	if (!flag) 
		rep(i , 1 , n + 1) {
			lo[i - 1] = i;
			st.insert(i - 1);
		}

	int L = 0;
	rep(i , n + 1, mx + 1) {
		if (~pos[i]) {
			B[L++] = lo[pos[i]];
			st.erase(pos[i]);
		}
		else {
			int v = *st.begin();
			B[L++] = lo[v];
			lo[v] = i;
		}
	}	
	return L;

}

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

const int MOD = 1e9 + 9;

typedef long long ll;
ll po(ll a , ll b) { return b ? po(a * a % MOD, b >> 1) * (b & 1 ? a : 1) % MOD : 1; }


int countReplacement(int n, int A[])
{

	if(!valid(n , A)) return 0;
 

	ll res = 1;

	int cnt = n;

	int last = -1;

	while (!mp.empty() && mp.begin()->first <= n) {
		cnt--;
		last = mp.begin()->first;
		mp.erase(mp.begin());
	}

	if(last == -1) res = n;

  
	last = n;

  int pp;
	while(!mp.empty()) {
		int me = mp.begin()->first;
      assert(me - last - 1 >= 0);
		res = (res * po(cnt , me - last - 1)) % MOD;
		last = me;
		cnt--;
      pp = mp.size();
		mp.erase(mp.begin());
		assert(pp != mp.size());
    }

	return res;

}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from gondola.cpp:2:
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:125:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(pp != mp.size());
          ~~~^~~~~~~~~~~~

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