oj.uz

Submission #57709

# Submission time Handle Problem Language Result Execution time Memory
57709 2018-07-15T21:21:24 Z FLDutchman Gondola (IOI14_gondola) C++14
60 / 100
 40 ms 3092 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 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; }
        while(inputSeq[i] > j) res = res * (n-i) % mod, j++; 
        j++;
    } 
    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 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 8 ms 1336 KB Output is correct
7 Correct 27 ms 1992 KB Output is correct
8 Correct 14 ms 1992 KB Output is correct
9 Correct 10 ms 1992 KB Output is correct
10 Correct 17 ms 1992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1992 KB Output is correct
2 Correct 2 ms 1992 KB Output is correct
3 Correct 2 ms 1992 KB Output is correct
4 Correct 2 ms 1992 KB Output is correct
5 Correct 3 ms 1992 KB Output is correct
6 Correct 9 ms 1992 KB Output is correct
7 Correct 30 ms 2164 KB Output is correct
8 Correct 16 ms 2164 KB Output is correct
9 Correct 6 ms 2164 KB Output is correct
10 Correct 21 ms 2164 KB Output is correct
11 Correct 2 ms 2164 KB Output is correct
12 Correct 3 ms 2164 KB Output is correct
13 Correct 13 ms 2164 KB Output is correct
14 Correct 3 ms 2164 KB Output is correct
15 Correct 28 ms 2164 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2164 KB Output is correct
2 Correct 2 ms 2164 KB Output is correct
3 Correct 2 ms 2164 KB Output is correct
4 Correct 2 ms 2164 KB Output is correct
5 Correct 3 ms 2164 KB Output is correct
6 Correct 2 ms 2164 KB Output is correct
7 Correct 3 ms 2164 KB Output is correct
8 Correct 4 ms 2164 KB Output is correct
9 Correct 2 ms 2164 KB Output is correct
10 Correct 3 ms 2164 KB Output is correct
11 Correct 27 ms 2328 KB Output is correct
12 Correct 19 ms 2604 KB Output is correct
13 Correct 40 ms 2804 KB Output is correct
14 Correct 17 ms 2804 KB Output is correct
15 Correct 29 ms 3092 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3092 KB Output is correct
2 Correct 2 ms 3092 KB Output is correct
3 Correct 2 ms 3092 KB Output is correct
4 Correct 3 ms 3092 KB Output is correct
5 Correct 2 ms 3092 KB Output is correct
6 Correct 2 ms 3092 KB Output is correct
7 Incorrect 2 ms 3092 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 3092 KB Output is correct
2 Correct 3 ms 3092 KB Output is correct
3 Correct 2 ms 3092 KB Output is correct
4 Correct 2 ms 3092 KB Output is correct
5 Correct 3 ms 3092 KB Output is correct
6 Correct 2 ms 3092 KB Output is correct
7 Incorrect 2 ms 3092 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 3092 KB Output is correct
2 Correct 3 ms 3092 KB Output is correct
3 Correct 2 ms 3092 KB Output is correct
4 Correct 2 ms 3092 KB Output is correct
5 Correct 2 ms 3092 KB Output is correct
6 Correct 3 ms 3092 KB Output is correct
7 Incorrect 2 ms 3092 KB Output isn't correct
8 Halted 0 ms 0 KB -