답안 #58880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58880	2018-07-19T18:04:17 Z	muradeyn	곤돌라 (IOI14_gondola)	C++14	컴파일 오류	0 ms	0 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009LL

long long powmod(int a,int b) {
    if (b == 0)return 1;
    if (b == 1)return a;
    long long lilhelp = powmod(a,b/2);
    long long ret = (lilhelp * lilhelp) % MOD;
    if (b % 2 == 1) ret = (ret * a) % MOD;
    return ret;
}

int valid(int n, int inputSeq[])
{
    std::set<int>st;
    int ls = -1,in;
    for (int i = 0;i<n;i++) {
        st.insert(inputSeq[i]);
        if (inputSeq[i] <= n) {
            if (ls == -1) {
                in = i;
                ls = inputSeq[i];
                continue;
            }
            if (inputSeq[i] < ls) {
                if (inputSeq[i] != 1)return 0;
                else if (ls - inputSeq[i] != n - i + in)return 0;
            }
            else {
                if (inputSeq[i] - ls != i - in)return 0;
            }
            in = i;
            ls = inputSeq[i];
        }
    }
    if (st.size() != n)return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int in[n],le = 0,idx = -1 , sz = 0;
    std::vector< std::pair<int,int> >v;
    for (int i = 0;i<n;i++) in[i] = i + 1;
    for (int i = 0;i<n;i++) {
        if (gondolaSeq[i] <= n) {
            idx = i;
            in[i] = gondolaSeq[i];
        }
        else {
            v.push_back(std::make_pair(gondolaSeq[i],i));
            sz++;
        }
    }
    std::sort(v.begin(),v.end());
    if (idx != -1) {
        int l = idx - 1,r = idx + 1;
        while (l >= 0) {
            if (in[l + 1] == 1)in[l] = n;
            else in[l] = in[l + 1] - 1;
            l--;
        }
        while (r < n) {
            if (in[r - 1] == n)in[r] = 1;
            else in[r] = in[r - 1] + 1;
            r++;
        }
    }
    for (int i = 0;i<sz;i++) {
        if (i == 0) {
            replacementSeq[le++] = in[v[i].second];
            int k = n + 1;
            while (k < v[i].first) {
                replacementSeq[le++] = k;
                k++;
            }
        }
        else {
            replacementSeq[le++] = in[v[i].second];
            int k = v[i - 1].first + 1;
            while (k < v[i].first) {
                replacementSeq[le++] = k;
                k++;
            }
        }
        /*std::cout<<i<<" "<<le<<std::endl;
        for (int j = 0;j<le;j++) std::cout<<replacementSeq[j]<<" ";
        std::cout<<std::endl;*/
    }
    return le;
}

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

int countReplacement(int n, int a[]) {
    if(!valid(n, a)) return 0; 
    long long ans = 1; 
    vector<int> v;
    for(int i = 0; i < n; i++) 
        if(a[i] > n) v.push_back(a[i]); 
    sort(v.begin(), v.end()); 
    for(int i = 0; i < v.size(); i++) {
        int rem = v.size() - i; 
        int tot = v[i] - (i ? v[i - 1] + 1 : n + 1); 
        ans *= powmod(rem, tot); 
        ans %= MOD; 
    } 
    if(v.size() == n) 
        ans = ans * n % MOD; 
    return ans; 
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (st.size() != n)return 0;
         ~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:101:5: error: 'vector' was not declared in this scope
     vector<int> v;
     ^~~~~~
gondola.cpp:101:5: note: suggested alternative:
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from gondola.cpp:2:
/usr/include/c++/7/bits/stl_vector.h:216:11: note:   'std::vector'
     class vector : protected _Vector_base<_Tp, _Alloc>
           ^~~~~~
gondola.cpp:101:12: error: expected primary-expression before 'int'
     vector<int> v;
            ^~~
gondola.cpp:103:22: error: 'v' was not declared in this scope
         if(a[i] > n) v.push_back(a[i]); 
                      ^
gondola.cpp:104:10: error: 'v' was not declared in this scope
     sort(v.begin(), v.end()); 
          ^
gondola.cpp:104:5: error: 'sort' was not declared in this scope
     sort(v.begin(), v.end()); 
     ^~~~
gondola.cpp:104:5: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from gondola.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:4856:5: note:   'std::sort'
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^~~~