oj.uz

Submission #57707

# Submission time Handle Problem Language Result Execution time Memory
57707 2018-07-15T21:19:43 Z FLDutchman Gondola (IOI14_gondola) C++14
60 / 100
 30 ms 4272 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+7;
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;
}

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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 564 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 572 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 8 ms 1352 KB Output is correct
7 Correct 22 ms 2116 KB Output is correct
8 Correct 13 ms 2116 KB Output is correct
9 Correct 6 ms 2116 KB Output is correct
10 Correct 18 ms 2116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2116 KB Output is correct
2 Correct 2 ms 2116 KB Output is correct
3 Correct 2 ms 2116 KB Output is correct
4 Correct 3 ms 2116 KB Output is correct
5 Correct 2 ms 2116 KB Output is correct
6 Correct 9 ms 2116 KB Output is correct
7 Correct 23 ms 2116 KB Output is correct
8 Correct 13 ms 2116 KB Output is correct
9 Correct 7 ms 2116 KB Output is correct
10 Correct 17 ms 2116 KB Output is correct
11 Correct 3 ms 2116 KB Output is correct
12 Correct 2 ms 2116 KB Output is correct
13 Correct 12 ms 2116 KB Output is correct
14 Correct 2 ms 2116 KB Output is correct
15 Correct 26 ms 2668 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 21 ms 3356 KB Output is correct
12 Correct 20 ms 3724 KB Output is correct
13 Correct 23 ms 4024 KB Output is correct
14 Correct 18 ms 4024 KB Output is correct
15 Correct 30 ms 4272 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4272 KB Output is correct
2 Correct 2 ms 4272 KB Output is correct
3 Correct 2 ms 4272 KB Output is correct
4 Correct 2 ms 4272 KB Output is correct
5 Correct 2 ms 4272 KB Output is correct
6 Correct 3 ms 4272 KB Output is correct
7 Incorrect 2 ms 4272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4272 KB Output is correct
2 Correct 2 ms 4272 KB Output is correct
3 Correct 3 ms 4272 KB Output is correct
4 Correct 2 ms 4272 KB Output is correct
5 Correct 4 ms 4272 KB Output is correct
6 Correct 2 ms 4272 KB Output is correct
7 Incorrect 2 ms 4272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4272 KB Output is correct
2 Correct 2 ms 4272 KB Output is correct
3 Correct 3 ms 4272 KB Output is correct
4 Correct 2 ms 4272 KB Output is correct
5 Correct 2 ms 4272 KB Output is correct
6 Correct 2 ms 4272 KB Output is correct
7 Incorrect 2 ms 4272 KB Output isn't correct
8 Halted 0 ms 0 KB -