Submission #136242

#	Time	Username	Problem	Language	Result	Execution time	Memory
136242		vince	Gondola (IOI14_gondola)	C++14	35 / 100	36 ms	5496 KiB

gondola

#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;
}

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

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]);
        pos[A[i]] = i;
    }
    if(A[0] > n)
    {
        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)
        {
            if(gondolaSeq[pos[mx]]  == A[pos[mx]]) assert(0);
            replacementSeq[sz++] = A[pos[mx]];
            A[pos[mx]] = i;
            
        }
        else
        {
            if(gondolaSeq[pos[i]]  == A[pos[i]]) assert(0);
            replacementSeq[sz++] = A[pos[i]],
            A[pos[i]] = i;
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(A[pos[gondolaSeq[i]]] > gondolaSeq[i])
            assert(0);
    }

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

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

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

Compilation message (stderr)

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;
            ~~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10