oj.uz

Submission #775218

# Submission time Handle Problem Language Result Execution time Memory
775218 2023-07-06T08:50:36 Z danikoynov Gondola (IOI14_gondola) C++14
90 / 100
 43 ms 13760 KB 
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 3e5 + 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 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 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 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 6 ms 596 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 0 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 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 596 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 284 KB Output is correct
9 Correct 1 ms 340 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 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 1220 KB Output is correct
12 Correct 7 ms 1364 KB Output is correct
13 Correct 9 ms 1972 KB Output is correct
14 Correct 7 ms 1240 KB Output is correct
15 Correct 15 ms 3184 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 212 KB Output is correct
3 Correct 1 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct

Subtask #9
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 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 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 31 ms 7024 KB Output is correct
10 Correct 24 ms 5708 KB Output is correct
11 Correct 11 ms 3296 KB Output is correct
12 Correct 13 ms 3284 KB Output is correct
13 Correct 4 ms 1216 KB Output is correct

Subtask #10
0 / 10.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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 33 ms 7060 KB Output is correct
10 Correct 29 ms 5760 KB Output is correct
11 Correct 11 ms 3308 KB Output is correct
12 Correct 12 ms 3284 KB Output is correct
13 Correct 4 ms 1212 KB Output is correct
14 Runtime error 43 ms 13760 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -