제출 #136646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136646		vince	곤돌라 (IOI14_gondola)	C++14	100 / 100	73 ms	6052 KiB

gondola

#include "gondola.h"
#include <set>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <vector>
#include <algorithm>
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;
    }
    
    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;
    }
    if(A[0] > n)
    {
        for(int i = 0; i < n; i++)
        {
            A[i] = i+1;
        }
    }
    
//    for(int i = 0; i < n; i++)
//        printf("%d\n", A[i]);
    
    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])
//            printf("%d %d %d\n", i, A[i], gondolaSeq[i]);
    }
//    printf("\n");
    
    
    return sz;
}


 
//----------------------
 
const long long MOD = 1e9+9;
bool ada[500003];

long long pwr(long long a, long long b)
{
	if(b == 0) return 1;
	else if(b == 2) return (a*a)%MOD;
	else if(b&1) return (pwr(a,b-1)*a)%MOD;
	else return pwr(pwr(a,b/2), 2);
}

int countReplacement(int n, int inputSeq[])
{

    if(!valid(n, inputSeq))
        return 0;
    
    long long res = 1;
    long long hit = 0;
    int mx = 0;
    
    vector<long long> vec;
    for(int i = 0; i < n; i++)
    {
        if(inputSeq[i] > n) hit++;
        if(inputSeq[i] > n) vec.push_back(inputSeq[i]);
        
    }
    if(hit == n) res = n;

    sort(vec.begin(), vec.end());
    
    long long bef = n;
    for(int i = 0; i < vec.size(); i++)
    {
    	res = (res*pwr(hit,vec[i]-bef-1))%MOD;
    	hit--;
    	bef = vec[i];
    }
    
    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:21:26: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
         if(inputSeq[idx] <= n & num != inputSeq[idx])
            ~~~~~~~~~~~~~~^~~~
gondola.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return st.size() == n;
            ~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); i++)
                    ~~^~~~~~~~~~~~
gondola.cpp:126:9: warning: unused variable 'mx' [-Wunused-variable]
     int mx = 0;
         ^~

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