oj.uz

Submission #57711

# Submission time Handle Problem Language Result Execution time Memory
57711 2018-07-15T21:25:45 Z FLDutchman Gondola (IOI14_gondola) C++14
100 / 100
 45 ms 6732 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef int INT;
 
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
 
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;
 
const ll INF = 1000000000000000000LL;
const int NMAX = 1e5+4;
const int mod = 1e9+9;
const ld eps = 1e-10;
const ld PI = acos(-1);
 
INT valid(INT n, INT inputSeq[]){
    int k = -1;
    FOR(i, 0, n) if(inputSeq[i] <= n) {k = i; break;} 
    if(k == -1) {
        vi tmp;
        FOR(i, 0, n) tmp.pb(inputSeq[i]);
        sort(tmp.begin(), tmp.end());
        FOR(i, 0, n-1) if(tmp[i] == tmp[i+1]) return false;
        return true;
    }
    int pos = (k-inputSeq[k]+1+n)%n;
    rotate(inputSeq, inputSeq+pos, inputSeq+n);
    vi tmp;
    FOR(i, 0, n) tmp.pb(inputSeq[i]);
    sort(tmp.begin(), tmp.end());
    FOR(i, 0, n-1) if(tmp[i] == tmp[i+1]) return false;
    FOR(i, 0, n){
        if(inputSeq[i] <= n and inputSeq[i] != i+1) return false; 
    }
    return true;
}
 
INT replacement(INT n, INT gondolaSeq[], INT replacementSeq[]){
    valid(n, gondolaSeq);
    vii seq(n);
    FOR(i, 0, n) seq[i] = {gondolaSeq[i], i+1};
    sort(&seq[0], &seq[n]);
    int j = n+1;
    vi ret;
    FOR(i, 0, n){
        while(seq[i].fst != seq[i].snd) ret.pb(seq[i].snd), seq[i].snd = j++;
    }
    FOR(i, 0, ret.size()) replacementSeq[i] = ret[i];
    return ret.size();
}
 
int mpow(int a, int b){
    if(b==0) return 1;
    if(b&1) return a*mpow(a, b-1)%mod;
    return mpow(a*a%mod, b>>1);
}
 
INT countReplacement(INT n, INT inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    int res = 1;
    sort(inputSeq, inputSeq+n);
    int j = n+1;
    bool all = 1;
    FOR(i, 0, n){
        if(inputSeq[i] <= n) { all = 0; continue; }
        res = res * mpow(n-i, inputSeq[i]-j) % mod;
        j = inputSeq[i]+1;
    } 
    if(all) res = res * n % mod;
    return res;
}
/*
signed main(){
    int n;
    INT seq[NMAX], outSeq[NMAX];
    cin >> n;
    FOR(i, 0, n) cin >> seq[i];
    //int l = replacement(n, seq, outSeq);
    //FOR(i, 0, l) cout << outSeq[i] << " ";
    //cout << endl;
    cout<<countReplacement(n, seq)<<endl;
    fast_io();
}*/

Compilation message

gondola.cpp: In function 'INT replacement(INT, INT*, INT*)':
gondola.cpp:14:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
gondola.cpp:63:5: note: in expansion of macro 'FOR'
     FOR(i, 0, ret.size()) replacementSeq[i] = ret[i];
     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 KB Output is correct
2 Correct 2 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 10 ms 1376 KB Output is correct
7 Correct 28 ms 2008 KB Output is correct
8 Correct 16 ms 2016 KB Output is correct
9 Correct 7 ms 2016 KB Output is correct
10 Correct 20 ms 2292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2292 KB Output is correct
2 Correct 3 ms 2292 KB Output is correct
3 Correct 2 ms 2292 KB Output is correct
4 Correct 2 ms 2292 KB Output is correct
5 Correct 4 ms 2292 KB Output is correct
6 Correct 8 ms 2292 KB Output is correct
7 Correct 22 ms 2292 KB Output is correct
8 Correct 13 ms 2292 KB Output is correct
9 Correct 7 ms 2292 KB Output is correct
10 Correct 17 ms 2292 KB Output is correct
11 Correct 2 ms 2292 KB Output is correct
12 Correct 2 ms 2292 KB Output is correct
13 Correct 16 ms 2292 KB Output is correct
14 Correct 3 ms 2292 KB Output is correct
15 Correct 25 ms 2292 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2292 KB Output is correct
2 Correct 2 ms 2292 KB Output is correct
3 Correct 2 ms 2292 KB Output is correct
4 Correct 2 ms 2292 KB Output is correct
5 Correct 3 ms 2292 KB Output is correct
6 Correct 2 ms 2292 KB Output is correct
7 Correct 3 ms 2292 KB Output is correct
8 Correct 3 ms 2292 KB Output is correct
9 Correct 3 ms 2292 KB Output is correct
10 Correct 4 ms 2292 KB Output is correct
11 Correct 18 ms 2340 KB Output is correct
12 Correct 29 ms 2516 KB Output is correct
13 Correct 22 ms 2824 KB Output is correct
14 Correct 26 ms 2824 KB Output is correct
15 Correct 32 ms 3220 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3220 KB Output is correct
2 Correct 2 ms 3220 KB Output is correct
3 Correct 2 ms 3220 KB Output is correct
4 Correct 2 ms 3220 KB Output is correct
5 Correct 3 ms 3220 KB Output is correct
6 Correct 2 ms 3220 KB Output is correct
7 Correct 3 ms 3220 KB Output is correct
8 Correct 4 ms 3220 KB Output is correct
9 Correct 30 ms 3220 KB Output is correct
10 Correct 24 ms 3220 KB Output is correct
11 Correct 15 ms 3220 KB Output is correct
12 Correct 13 ms 3220 KB Output is correct
13 Correct 8 ms 3220 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3220 KB Output is correct
2 Correct 2 ms 3220 KB Output is correct
3 Correct 3 ms 3220 KB Output is correct
4 Correct 3 ms 3220 KB Output is correct
5 Correct 2 ms 3220 KB Output is correct
6 Correct 2 ms 3220 KB Output is correct
7 Correct 2 ms 3220 KB Output is correct
8 Correct 2 ms 3220 KB Output is correct
9 Correct 31 ms 3852 KB Output is correct
10 Correct 23 ms 3852 KB Output is correct
11 Correct 14 ms 3852 KB Output is correct
12 Correct 13 ms 3852 KB Output is correct
13 Correct 5 ms 3852 KB Output is correct
14 Correct 45 ms 5472 KB Output is correct
15 Correct 44 ms 6420 KB Output is correct
16 Correct 10 ms 6420 KB Output is correct
17 Correct 25 ms 6496 KB Output is correct
18 Correct 15 ms 6732 KB Output is correct