oj.uz

Submission #57704

# Submission time Handle Problem Language Result Execution time Memory
57704 2018-07-15T21:08:54 Z FLDutchman Gondola (IOI14_gondola) C++14
55 / 100
 35 ms 4856 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[]){

}
/*
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;
    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];
     ^~~
gondola.cpp: In function 'INT countReplacement(INT, INT*)':
gondola.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 516 KB Output is correct
3 Correct 2 ms 516 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 9 ms 1480 KB Output is correct
7 Correct 24 ms 2060 KB Output is correct
8 Correct 13 ms 2060 KB Output is correct
9 Correct 6 ms 2060 KB Output is correct
10 Correct 17 ms 2060 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2060 KB Output is correct
2 Correct 3 ms 2060 KB Output is correct
3 Correct 2 ms 2060 KB Output is correct
4 Correct 3 ms 2060 KB Output is correct
5 Correct 3 ms 2060 KB Output is correct
6 Correct 3 ms 2060 KB Output is correct
7 Correct 3 ms 2060 KB Output is correct
8 Correct 3 ms 2060 KB Output is correct
9 Correct 2 ms 2060 KB Output is correct
10 Correct 4 ms 2060 KB Output is correct
11 Correct 34 ms 2724 KB Output is correct
12 Correct 29 ms 3656 KB Output is correct
13 Correct 26 ms 4048 KB Output is correct
14 Correct 21 ms 4048 KB Output is correct
15 Correct 35 ms 4856 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -