Submission #256516

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256516	2020-08-02T19:13:46 Z	PedroBigMan	Gondola (IOI14_gondola)	C++14	100 / 100	38 ms	5044 KB

gondola

#include "gondola.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000009LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

ll fastexp(ll a,ll e) 
{
    if(e==0) {return 1LL;}
    if(e%2LL==0)
    {
        ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod;
    }
    else
    {
        ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod;
    }
}

int valid(int n, int inputSeq[])
{
    ll N=(ll) n;
    vector<ll> s; REP(i,0,N) {s.pb((ll) inputSeq[i]);}
    vector<ll> copy = s; sort(whole(copy));
    REP(i,0,N-1) {if(copy[i]==copy[i+1]) {return 0;}}
    REP(i,0,N) {if(s[i]>N) {s[i]=-1;} else {s[i]--;}}
    ll fi=-1;
    REP(i,0,N) {if(s[i]!=-1) {fi=i; break;}}
    if(fi==-1) {return 1;}
    REP(i,0,N)
    {
        if(s[i]==-1) {continue;}
        if(((s[i]-i)-(s[fi]-fi))%N!=0) {return 0;}
    }
    return 1;
 }

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

int replacement(int n, int gondolaSeq[], int r[])
{
    ll N =(ll) n; vector<ll> s; REP(i,0,N) {s.pb((ll) gondolaSeq[i]);}
    REP(i,0,N) 
    {
        if(s[i]<=N) 
        {
            ll shift = (s[i]-1LL-i)%N; //shift to the right
            vector<ll> copy_s; REP(j,0,N) {copy_s.pb(s[(j-shift+N)%N]);}
            s=copy_s; break;
        }
    }
    ll max_ind = (ll) (max_element(whole(s))-s.begin());
    ll R = s[max_ind]-N;
    unordered_map<ll,ll> m; 
    REP(i,0,N) {m[s[i]]=i;}
    ll last = max_ind+1;
    REP(i,0,R)
    {
        ll val = N+i+1;
        unordered_map<ll,ll>::iterator it = m.find(val);
        if(it==m.end()) {r[i]=last; last=val;}
        else if(m[val]!=max_ind) {r[i]=m[val]+1;}
        else {r[i]=last; last=val;}
    }
    return R;
}

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

int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq)) {return 0;}
    ll N =(ll) n; vector<ll> s; REP(i,0,N) {s.pb((ll) inputSeq[i]);}
    vector<ll> p;
    REP(i,0,N) {if(s[i]<=N) {continue;} p.pb(s[i]-N);}
    sort(whole(p));
    REP(i,0,p.size()) {p[i]-=(i+1);}
    ll ans=1LL;
    ll last=0LL;
    REP(i,0,p.size())
    {
        ll val = fastexp(p.size()-i,p[i]-last); ans*=val; ans%=mod;
        last=p[i];
    }
    if(*min_element(whole(s))>N) {ans*=N;}
    ans+=mod; ans%=mod;
    return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	256 KB	Output is correct
2	Correct	256 KB	Output is correct
3	Correct	384 KB	Output is correct
4	Correct	384 KB	Output is correct
5	Correct	256 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	8 ms	1148 KB	Output is correct
7	Correct	20 ms	2164 KB	Output is correct
8	Correct	13 ms	1908 KB	Output is correct
9	Correct	5 ms	892 KB	Output is correct
10	Correct	20 ms	2036 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	9 ms	1148 KB	Output is correct
7	Correct	19 ms	2164 KB	Output is correct
8	Correct	14 ms	1908 KB	Output is correct
9	Correct	5 ms	892 KB	Output is correct
10	Correct	18 ms	2036 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	10 ms	1148 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	21 ms	2164 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	20 ms	4560 KB	Output is correct
12	Correct	22 ms	5044 KB	Output is correct
13	Correct	19 ms	2536 KB	Output is correct
14	Correct	20 ms	4496 KB	Output is correct
15	Correct	26 ms	2320 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct

Subtask #8
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	26 ms	2164 KB	Output is correct
10	Correct	20 ms	1848 KB	Output is correct
11	Correct	8 ms	1052 KB	Output is correct
12	Correct	10 ms	1100 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	27 ms	2164 KB	Output is correct
10	Correct	20 ms	1840 KB	Output is correct
11	Correct	8 ms	1052 KB	Output is correct
12	Correct	10 ms	1100 KB	Output is correct
13	Correct	3 ms	524 KB	Output is correct
14	Correct	33 ms	3796 KB	Output is correct
15	Correct	38 ms	4216 KB	Output is correct
16	Correct	7 ms	1124 KB	Output is correct
17	Correct	24 ms	2704 KB	Output is correct
18	Correct	14 ms	1864 KB	Output is correct

Submission #256516

Compilation message