답안 #77760 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77760	2018-09-30T08:47:19 Z	Charis02	곤돌라 (IOI14_gondola)	C++14	100 / 100	51 ms	13128 KB

gondola

#include "gondola.h"
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXNUM 250002

using namespace std;

ll go[MAXNUM],freq2[MAXNUM];
map < ll,ll > freq;

int valid(int n, int inputSeq[])
{
    ll mini = 0;

    rep(i,0,n)
    {
        if(inputSeq[i] < inputSeq[mini])
        {
            mini = i;
        }

        freq[inputSeq[i]]++;
    }

    if(freq.size() != n)
        return false;

    ll cur = 1;
    ll num = (inputSeq[mini] > n) ? 1 : inputSeq[mini];

    rep(i,mini-num+1,mini+n-num+1)
    {
        ll x = (i+2*n)%n;

        if(inputSeq[x] > n)
            continue;

        if(inputSeq[x] != cur)
        {
            return false;
        }

        cur++;
    }

    return true;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    ll mini = 0;
    ll maxi = 0;

    rep(i,0,n)
    {
        if(gondolaSeq[i] < gondolaSeq[mini])
        {
            mini = i;
        }

        if(gondolaSeq[i] > gondolaSeq[maxi])
        {
            maxi = i;
        }
    }

    ll num = (gondolaSeq[mini] > n) ? 1 : gondolaSeq[mini];
    ll cur = 1;

    rep(x,mini-num+1,mini+n-num+1)
    {
        ll i = (x+2*n)%n;

        if(gondolaSeq[i] > n)
        {
            freq2[gondolaSeq[i]]++;
        }

//        cout << x << " " << gondolaSeq[i] << " " << cur<< endl;

        go[gondolaSeq[i]] = cur;

        cur++;
    }

    ll countt = 0;
    ll prev = go[gondolaSeq[maxi]];

    rep(i,n+1,gondolaSeq[maxi]+1)
    {
        if(i == gondolaSeq[maxi] || freq2[i] == 0)
        {
            replacementSeq[countt] = prev;
            prev = i;
        }
        else
        {
            replacementSeq[countt] = go[i];
        }

        countt++;
    }

    return countt;
}

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

ll mod = 1000000009;

ll fast_expo(ll vasi,ll ek)
{
    if(ek == 0)
        return 1;
    if(ek == 1)
        return vasi;

    unsigned ll x = fast_expo(vasi,ek/2);

    x = (x*x)%mod;

    if(ek%2==1)
    {
        x = (x*vasi)%mod;
    }

    return x;
}

int countReplacement(int n, int inputSeq[])
{
    ll countt = 0;
    ll maxi = 0;

    rep(i,0,n)
    {
        if(inputSeq[i] > n)
        {
            countt++;
        }

        if(inputSeq[i] > inputSeq[maxi])
        {
            maxi = i;
        }
    }
/*
    if(countt == 0)
    {
        ll cur = 1;

        rep(i,maxi+1,maxi+n+1)
        {
            ll x = i%n;

            if(inputSeq[x] != cur)
            {
                return 0;
            }

            cur++;
        }
    }
*/
    sort(inputSeq,inputSeq+n);
    unsigned ll res = 1;
    ll prev = n;

    if(countt == n)
        res = n;


    rep(i,0,n)
    {
        if(inputSeq[i] <= n)
            continue;

        res = (res*fast_expo(countt%mod,inputSeq[i] - prev - 1))%mod;
        prev = inputSeq[i];
        countt--;
    }

    return res;
}

/*
int main()
{
    ll q,n,ar[MAXNUM],res[MAXNUM];

    cin >> q >> n;

    rep(i,0,n)
    {
        cin >> ar[i];
    }

    if(q <= 3)
    {
        cout << valid(n,ar) << endl;
    }
    else if(q <= 6)
    {
        ll ans = replacement(n,ar,res);
        cout << ans << " ";

        rep(i,0,ans)
        {
            cout << res[i] << " ";
        }

        cout << endl;
    }
    else
    {
        cout << countReplacement(n,ar) << endl;
    }
}
*/

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(freq.size() != n)
        ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	2 ms	708 KB	Output is correct
4	Correct	2 ms	756 KB	Output is correct
5	Correct	2 ms	764 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	764 KB	Output is correct
2	Correct	2 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	2 ms	968 KB	Output is correct
5	Correct	2 ms	968 KB	Output is correct
6	Correct	18 ms	3540 KB	Output is correct
7	Correct	42 ms	5808 KB	Output is correct
8	Correct	35 ms	6584 KB	Output is correct
9	Correct	11 ms	6584 KB	Output is correct
10	Correct	41 ms	8060 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	8060 KB	Output is correct
2	Correct	2 ms	8060 KB	Output is correct
3	Correct	2 ms	8060 KB	Output is correct
4	Correct	2 ms	8060 KB	Output is correct
5	Correct	2 ms	8060 KB	Output is correct
6	Correct	17 ms	8060 KB	Output is correct
7	Correct	42 ms	8060 KB	Output is correct
8	Correct	36 ms	8532 KB	Output is correct
9	Correct	11 ms	8532 KB	Output is correct
10	Correct	40 ms	9952 KB	Output is correct
11	Correct	2 ms	9952 KB	Output is correct
12	Correct	2 ms	9952 KB	Output is correct
13	Correct	21 ms	9952 KB	Output is correct
14	Correct	2 ms	9952 KB	Output is correct
15	Correct	51 ms	10836 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct
6	Correct	2 ms	10836 KB	Output is correct
7	Correct	3 ms	10836 KB	Output is correct
8	Correct	2 ms	10836 KB	Output is correct
9	Correct	3 ms	10836 KB	Output is correct
10	Correct	3 ms	10836 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	3 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct
6	Correct	2 ms	10836 KB	Output is correct
7	Correct	2 ms	10836 KB	Output is correct
8	Correct	2 ms	10836 KB	Output is correct
9	Correct	2 ms	10836 KB	Output is correct
10	Correct	2 ms	10836 KB	Output is correct
11	Correct	19 ms	10836 KB	Output is correct
12	Correct	25 ms	10836 KB	Output is correct
13	Correct	16 ms	10836 KB	Output is correct
14	Correct	12 ms	10836 KB	Output is correct
15	Correct	23 ms	10836 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct
6	Correct	2 ms	10836 KB	Output is correct
7	Correct	2 ms	10836 KB	Output is correct
8	Correct	2 ms	10836 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct
6	Correct	2 ms	10836 KB	Output is correct
7	Correct	2 ms	10836 KB	Output is correct
8	Correct	2 ms	10836 KB	Output is correct
9	Correct	20 ms	10836 KB	Output is correct
10	Correct	16 ms	10836 KB	Output is correct
11	Correct	8 ms	10836 KB	Output is correct
12	Correct	9 ms	10836 KB	Output is correct
13	Correct	4 ms	10836 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10836 KB	Output is correct
2	Correct	2 ms	10836 KB	Output is correct
3	Correct	2 ms	10836 KB	Output is correct
4	Correct	2 ms	10836 KB	Output is correct
5	Correct	2 ms	10836 KB	Output is correct
6	Correct	2 ms	10836 KB	Output is correct
7	Correct	2 ms	10836 KB	Output is correct
8	Correct	2 ms	10836 KB	Output is correct
9	Correct	22 ms	10836 KB	Output is correct
10	Correct	17 ms	10836 KB	Output is correct
11	Correct	8 ms	10836 KB	Output is correct
12	Correct	9 ms	10836 KB	Output is correct
13	Correct	3 ms	10836 KB	Output is correct
14	Correct	27 ms	11232 KB	Output is correct
15	Correct	49 ms	12300 KB	Output is correct
16	Correct	8 ms	12300 KB	Output is correct
17	Correct	20 ms	12888 KB	Output is correct
18	Correct	12 ms	13128 KB	Output is correct