oj.uz

Submission #775221

# Submission time Handle Problem Language Result Execution time Memory
775221 2023-07-06T08:51:02 Z danikoynov Gondola (IOI14_gondola) C++14
90 / 100
 58 ms 13772 KB 
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 10;

ll cnt[maxn];
int valid(int n, int inputSeq[])
{
    for (ll i = 0; i < n; i ++)
    {
        ll val = inputSeq[(i + 1) % n];

        if (inputSeq[i] == n && val == 1)
            continue;
        if (val != inputSeq[i] + 1)
        {
            ///cout << i << endl;
            ///cout << inputSeq[i] << " " << val << endl;
            return 0;
        }

    }
    return 1;
}

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

ll order[maxn], to_go[maxn];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    ll pivot = 0;
    while(pivot < n && gondolaSeq[pivot] > n)
        pivot ++;

    if (pivot == n)
    {
        pivot = 0;
        for (ll i = 0; i < n; i ++)
            order[i] = gondolaSeq[i];
    }
    else
    {
        order[gondolaSeq[pivot] - 1] = gondolaSeq[pivot];
        for (ll i = pivot + 1; i < n + pivot; i ++)
        {
            order[(gondolaSeq[pivot] - 1 + (i - pivot)) % n] = gondolaSeq[i % n];
        }
    }
    ///for (ll i = 0; i < n; i ++)
    ///cout << order[i] << " ";
    /// cout << endl;
    ll mx = 0, pt = 0;

    for (ll i = 0; i < n; i ++)
    {
        if (order[i] > n)
        {
            if (order[i] > mx)
            {
                mx = order[i];
                pt = i + 1;
            }
            to_go[order[i]] = i + 1;
        }
    }
    ///cout << mx << " " << pt << endl;

    ll idx = 0, last_free = pt;
    for (ll i = n + 1; i <= mx; i ++)
    {
        if (to_go[i] != 0)
        {
            if (to_go[i] == pt)
                replacementSeq[idx ++] = last_free;
            else
                replacementSeq[idx ++] = to_go[i];
        }
        else
        {
            replacementSeq[idx ++] = last_free;
            last_free = i;
        }
    }
    return max((ll)0, mx - n);
}

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


const ll mod = 1e9 + 9;
int countReplacement(int n, int inputSeq[])
{

    map < ll, ll > mp;
    for (ll i = 0; i < n; i ++)
    {
        if (mp[inputSeq[i]] != 0)
            return 0;
        mp[inputSeq[i]] = 1;
    }

     ll pivot = 0;
    while(pivot < n && inputSeq[pivot] > n)
        pivot ++;

    if (pivot == n)
    {
        pivot = 0;
        for (ll i = 0; i < n; i ++)
            order[i] = inputSeq[i];
    }
    else
    {
        order[inputSeq[pivot] - 1] = inputSeq[pivot];
        for (ll i = pivot + 1; i < n + pivot; i ++)
        {
            order[(inputSeq[pivot] - 1 + (i - pivot)) % n] = inputSeq[i % n];
        }
    }
    /**for (ll i = 0; i < n; i ++)
    cout << order[i] << " ";
     cout << endl;*/
    ll mx = 0, pt = 0;

    for (ll i = 0; i < n; i ++)
    {
        if (order[i] > n)
        {
            if (order[i] > mx)
            {
                mx = order[i];
                pt = i + 1;
            }
            to_go[order[i]] = i + 1;
        }
    }
    ///cout << mx << " " << pt << endl;
    ll sp = 0;
    for (ll i = 0; i < n; i ++)
        if (order[i] > n)
        sp ++;

    //cout << sp << endl;
    ll idx = 0, last_free = pt;
    ll ways = 1;
    if (sp == n)
        ways = n;
    for (ll i = n + 1; i <= mx; i ++)
    {
        if (ways == 0)
            return 0;
        if (to_go[i] != 0)
        {
            sp --;
            //if (to_go[i] == pt)
              //  replacementSeq[idx ++] = last_free;
            //else
              ///  replacementSeq[idx ++] = to_go[i];
        }
        else
        {
            ///cout << i << " : " << sp << " " << ways << endl;
            ways = (ways * sp) % mod;
            ///replacementSeq[idx ++] = last_free;
            ///last_free = i;
        }
    }
    return ways;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:145:8: warning: unused variable 'idx' [-Wunused-variable]
  145 |     ll idx = 0, last_free = pt;
      |        ^~~
gondola.cpp:145:17: warning: unused variable 'last_free' [-Wunused-variable]
  145 |     ll idx = 0, last_free = pt;
      |                 ^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 6 ms 568 KB Output is correct
7 Correct 7 ms 1064 KB Output is correct
8 Correct 6 ms 908 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 6 ms 1100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 6 ms 1072 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 5 ms 680 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 1064 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 7 ms 1620 KB Output is correct
12 Correct 10 ms 1876 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 7 ms 1620 KB Output is correct
15 Correct 16 ms 3308 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 46 ms 7084 KB Output is correct
10 Correct 33 ms 5804 KB Output is correct
11 Correct 11 ms 3284 KB Output is correct
12 Correct 12 ms 3248 KB Output is correct
13 Correct 4 ms 1136 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 31 ms 7008 KB Output is correct
10 Correct 25 ms 5724 KB Output is correct
11 Correct 10 ms 3284 KB Output is correct
12 Correct 15 ms 3296 KB Output is correct
13 Correct 4 ms 1224 KB Output is correct
14 Runtime error 58 ms 13772 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -