Submission #20817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20817	2017-02-16T12:45:38 Z	jjwdi0	Gondola (IOI14_gondola)	C++11	Compilation error	0 ms	0 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define MOD 1000000009
using namespace std;
typedef long long ll;
typedef pair<int, int> pr;

int N;
vector<int> v;
vector<pr> rpc;
map<int> same;

ll pow(ll x, int y) {
    if(!y) return 1LL;
    ll u = pow(x, y / 2);
    return y & 1 ? u * u % MOD * x % MOD : u * u % MOD;
}

int valid(int n, int inputSeq[]) {
    N = n;
    int idx = -1;
    for(int i=0; i<N; i++) same[inputSeq[i]]++;
    for(auto it : same) if(it.second > 1) return 0;
    for(int i=0; i<N; i++) {
        if(inputSeq[i] <= N) { idx = i; break; }
    }
    if(idx < 0) return 1;
    int u = inputSeq[idx];
    for(int i=idx; i<idx+N; i++) {
        if(inputSeq[i % N] > N) continue;
        if(inputSeq[i % N] != (u + (i - idx) - 1) % N + 1) return 0;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    N = n;
    int idx = 0, res = 0;
    for(int i=0; i<N; i++) {
        if(gondolaSeq[i] <= N) { idx = i; break; }
    }
    int u = gondolaSeq[idx] > N ? 1 : gondolaSeq[idx];
    for(int i=0; i<N; i++) if(gondolaSeq[i] > N) rpc.push_back(pr(gondolaSeq[i], i));
    sort(all(rpc));
    int p = N + 1;
    for(int i=0; i<sz(rpc); i++) {
        int t;
        if(rpc[i].second >= idx) t = (u + rpc[i].second - idx - 1) % N + 1;
        else t = (u + rpc[i].second + N - idx - 1) % N + 1;
        while(t < rpc[i].first) {
            replacementSeq[res++] = t;
            t = p++;
        }
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    N = n;
    if(!valid(N, inputSeq)) return 0;
    for(int i=0; i<N; i++) if(inputSeq[i] > N) v.push_back(inputSeq[i]);
    sort(all(v));
    ll res = (sz(v) == N ? N : 1LL), m = sz(v);
    int pre = N;
    for(int i=0; i<sz(v); i++) {
        res = res * pow(m, v[i] - pre - 1) % MOD;
        m--, pre = v[i];
    }
    return res;
}

Compilation message

gondola.cpp:13:8: error: wrong number of template arguments (1, should be at least 2)
 map<int> same;
        ^
In file included from /usr/include/c++/5/map:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:80,
                 from gondola.cpp:2:
/usr/include/c++/5/bits/stl_map.h:96:11: note: provided for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
     class map
           ^
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:24:44: error: invalid types 'int[int]' for array subscript
     for(int i=0; i<N; i++) same[inputSeq[i]]++;
                                            ^
gondola.cpp:25:19: error: 'begin' was not declared in this scope
     for(auto it : same) if(it.second > 1) return 0;
                   ^
gondola.cpp:25:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:94:0,
                 from gondola.cpp:2:
/usr/include/c++/5/valarray:1206:5: note:   'std::begin'
     begin(const valarray<_Tp>& __va)
     ^
/usr/include/c++/5/valarray:1206:5: note:   'std::begin'
gondola.cpp:25:19: error: 'end' was not declared in this scope
     for(auto it : same) if(it.second > 1) return 0;
                   ^
gondola.cpp:25:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:94:0,
                 from gondola.cpp:2:
/usr/include/c++/5/valarray:1226:5: note:   'std::end'
     end(const valarray<_Tp>& __va)
     ^
/usr/include/c++/5/valarray:1226:5: note:   'std::end'