oj.uz

Submission #12707

# Submission time Handle Problem Language Result Execution time Memory
12707 2015-01-01T11:28:26 Z qja0950 Gondola (IOI14_gondola) C++
55 / 100
 32 ms 4620 KB 
#include "gondola.h"

#define MAX_N 101101
#define MAX_V 250052

int CheckV[MAX_V];

int valid(int n, int inputSeq[])
{
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        CheckV[now]++;
        if(CheckV[now] > 1) return 0;
    }
    
    int first = -1;
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    if(first == -1) return 1;
    
    
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (inputSeq[first] + i - 1) % n + 1;
        
        int now = inputSeq[index];
        if(now > n) continue;
        if(now != value) return 0;
    }
    return 1;
}

//----------------------
#include <algorithm>

using namespace std;

struct SORTR{
    int index;
    int value;
}SortR[MAX_N];
bool operator<(SORTR X, SORTR Y) {
    return X.value < Y.value;
}

int State[MAX_N];


int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int first = 0;
    for(int i=0; i<n; i++) {
        int now = gondolaSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (gondolaSeq[first] + i - 1) % n + 1;
        State[index] = value;
        
        SortR[i].index = i;
        SortR[i].value = gondolaSeq[i];
    }
    sort(SortR, SortR+n);
    
    int cnt = 0;
    int now = n;
    for(int i=0; i<n; i++) {
        int nowindex = SortR[i].index;
        int nowvalue = SortR[i].value;
        if(nowvalue < n) continue;
        while(State[nowindex] != nowvalue) {
            replacementSeq[cnt++] = State[nowindex];
            State[nowindex] = ++now;
        }
    }
    return cnt;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4620 KB Output isn't correct - Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4620 KB Output isn't correct - Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4620 KB Output isn't correct - Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4620 KB Output isn't correct - Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -