Submission #136234

# Submission time Handle Problem Language Result Execution time Memory
136234 2019-07-25T04:25:57 Z vince Gondola (IOI14_gondola) C++14
20 / 100
36 ms 4524 KB
#include "gondola.h"
#include <set>
#include <stdio.h>
#include <string.h>
#include <assert.h>
using namespace std;

int valid(int n, int inputSeq[])
{
    set<int> st;
    int num = -1;
    for(int i = 0; i < n; i++)
    {
        st.insert(inputSeq[i]);
        int idx = i%n;
        if(inputSeq[idx] <= n && num == -1)
            num = inputSeq[idx];
        
        if(inputSeq[idx] <= n & num != inputSeq[idx])
            return 0;
        
        if(num != -1)
        {
            num++;
            if(num == n+1)
                num -= n;
        }
    }
    return st.size() == n;
}

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

bool ada[500003];
int A[500003];
int pos[500003];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    memset(pos, -1, sizeof pos);
    int mx = 0;
    for(int i = 0; i < n; i++)
    {
        A[i] = gondolaSeq[i];
        mx = max(mx, A[i]);
        ada[A[i]] = 1;
        pos[A[i]] = i;
    }
    if(A[0] > n)
    {
        assert(0);
        for(int i = 0; i < n; i++)
            A[i] = i+1;
    }
    
    for(int i = 0; i < 3*n; i++)
    {
        if(A[(i-1+n)%n] <= n)
            A[i%n] = A[(i-1+n)%n]+1;
        
        if(A[i%n] == n+1) A[i%n] = 1;
    }
    int sz = 0;
    for(int i = n+1; i <= mx; i++)
    {
//        printf("%d %d\n", i, pos[i]);
        if(pos[i] == -1)
            replacementSeq[sz++] = A[pos[mx]],
            A[pos[mx]] = i;
        else
            replacementSeq[sz++] = A[pos[i]],
            A[pos[i]] = i;
    }

    
//    for(int i = 0; i < n; i++)
//        printf("%d ", A[i]);
//    printf("\n");
    
    
    return sz;
}

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

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

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:19:26: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
         if(inputSeq[idx] <= n & num != inputSeq[idx])
            ~~~~~~~~~~~~~~^~~~
gondola.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return st.size() == n;
            ~~~~~~~~~~^~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 15 ms 2168 KB Output is correct
7 Correct 13 ms 632 KB Output is correct
8 Correct 27 ms 3960 KB Output is correct
9 Correct 10 ms 1528 KB Output is correct
10 Correct 34 ms 4472 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 15 ms 2296 KB Output is correct
7 Correct 13 ms 632 KB Output is correct
8 Correct 27 ms 3960 KB Output is correct
9 Correct 9 ms 1528 KB Output is correct
10 Correct 36 ms 4524 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 7 ms 504 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 14 ms 632 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 2268 KB Output is correct
2 Runtime error 7 ms 4384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Runtime error 8 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Runtime error 7 ms 4444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 420 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -