Submission #412528

#	Time	Username	Problem	Language	Result	Execution time	Memory
412528		Geothermal	Gondola (IOI14_gondola)	C++14	70 / 100	124 ms	5932 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000009;
const char nl = '\n';
const int MX = 250001; 


struct mi {
	ll v; explicit operator ll() const { return v; }
	mi() { v = 0; }
	mi(ll _v) { 
		v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mi& a, const mi& b) { 
		return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { 
		return !(a == b); }
	friend bool operator<(const mi& a, const mi& b) { 
		return a.v < b.v; }
   
	mi& operator+=(const mi& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	mi& operator-=(const mi& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	mi& operator*=(const mi& m) { 
		v = v*m.v%MOD; return *this; }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi pow(mi a, ll p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend mi inv(const mi& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mi operator-() const { return mi(-v); }
	mi& operator++() { return *this += 1; }
	mi& operator--() { return *this -= 1; }
    mi operator++(int) { mi temp; temp.v = v++; return temp; }
    mi operator--(int) { mi temp; temp.v = v--; return temp; }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
    friend ostream& operator<<(ostream& os, const mi& m) {
        os << m.v; return os;
    }
    friend istream& operator>>(istream& is, mi& m) {
        ll x; is >> x;
        m.v = x;
        return is;
    }
};


typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;


int valid(int N, int A[])
{
    int val = -1;
    set<int> found;
    F0R(i, N) {
        int X = A[i];
        if (found.count(X)) return 0;
        found.ins(X);
        if (val == -1 && X <= N) {
            val = (X - i + N) % N;
        } 
        if (X <= N && val != (X - i + N) % N) return 0;
    }
  return 1;
}

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

int replacement(int N, int A[], int res[])
{
    set<int> need;
    map<int, int> rep;
    int cur[N];
    int p = 0;
    F0R(i, N) {
        if (A[i] <= N) p = (i - A[i] + N + 1) % N;
    }
    F0R(i, N) {
        cur[i] = (i + N - p) % N + 1;
    }
    int hi = 0;
    F0R(i, N) {
        ckmax(hi, A[i]);
        if (A[i] > N) {
            need.ins(i); rep[A[i]] = i;
        }
    }
    int ans = hi - N;
    FOR(i, N+1, hi+1) {
        if (rep.count(i)) {
            res[i-N-1] = cur[rep[i]];
            need.erase(rep[i]);
        } else {
            res[i-N-1] = cur[*need.begin()];
        }
    }
  return ans;
}

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

int countReplacement(int N, int A[])
{
    if (valid(N, A) == 0) return 0;
    set<int> need;
    F0R(i, N) {
        if (A[i] > N) need.ins(A[i]);
    }
    int lst = N;
    int cnt = sz(need);
    mi ans = 1;
    if (cnt == N) {
        ans *= N;
    }
    trav(a, need) {
        ans *= pow(mi(cnt), a-lst-1);
        cnt--;
        lst = a;
    }

    return (int) ans.v;
}

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