oj.uz

Submission #1018374

# Submission time Handle Problem Language Result Execution time Memory
1018374 2024-07-09T21:03:40 Z n3rm1n Gondola (IOI14_gondola) C++17
100 / 100
 48 ms 8660 KB 
#include <bits/stdc++.h>
#include "gondola.h"
#define endl '\n'
using namespace std;
const int MAXN = 3e5 + 10;
map < int , int  > seen;
int valid(int n, int inputSeq[])
{
    int cnt = 0;
    int minim = 1e9;
    int minn = 1e9, maxx = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(seen[inputSeq[i]])return 0;
        if(inputSeq[i] <= n)cnt ++;
        else
        {
            minn = min(minn, inputSeq[i]);
            maxx = max(maxx, inputSeq[i]);
        }
        minim = min(minim, inputSeq[i]);
        seen[inputSeq[i]] = 1;
    }
    int left = n - cnt;
    //cout << left << " " << minn << " " << maxx << endl;
    //if(left != 0 && !(minn == n+1 && maxx == minn + left - 1))
        //return 0;

    //cout << "here " << endl;
    int seenit = 0, expected = minim;
    int onpoint = n+1;
    for (int i = 0; i < n; ++ i)
    {
        if(inputSeq[i] == minim)
            seenit = 1;
        if(!seenit)continue;
        if(inputSeq[i] > n)
        {
            expected ++;
        }
        else if(inputSeq[i] != expected)
        {
            return 0;
        }
        else expected ++;
    }
    for (int i = 0; i < n; ++ i)
    {
        if(inputSeq[i] == minim)
            break;

        if(inputSeq[i] > n)
        {
            expected ++;
        }
        else if(inputSeq[i] != expected)
        {
            return 0;
        }
        else expected ++;
    }
   return 1;
}
int place[MAXN];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    memset(place, -1, sizeof(place));
    int len;
    int maxim = 0, maxim_place = 0;
    int minim = 1e9, minim_index = 0;
    for (int i = 0; i < n; ++ i)
    {
        place[gondolaSeq[i]] = i ;

        if(gondolaSeq[i] <= n && minim > gondolaSeq[i])
        {
            minim = gondolaSeq[i];
            minim_index = i;
        }
        if(gondolaSeq[i] > maxim)
        {
            maxim = gondolaSeq[i];
            maxim_place = i;
        }
    }
    len = maxim - n;
    if(minim == 1e9)
    {


       int last = 0;
        for (int i = n+1; i <= maxim; ++ i)
        {
           // cout << "for val " << i << " " << place[i] << endl;
            if(place[i] != -1)
            {
                replacementSeq[i - n - 1] = place[i] + 1;
                last = place[i] + 1;
            }
        }

        int initlast = last;
        for (int i = n+1; i <= maxim; ++ i)
        {
            if(!replacementSeq[i - n - 1])
            {
                replacementSeq[i-n-1] = last;
                last = i;
            }
            else if(replacementSeq[i-n-1] == initlast)
            {
                replacementSeq[i-n-1] = last;
            }
        }
        return len;
    }
    int expected = 1;
    int starter = minim_index - (minim - 1);
    if(starter < 0)starter += n;

    int id = 0;
    for (int i = starter; i < n; ++ i)
    {

        if(gondolaSeq[i] != expected && gondolaSeq[i] >= n)
        {
            replacementSeq[gondolaSeq[i] - n - 1] = expected;
        }
        expected ++;
    }
    for (int i = 0; i < starter; ++ i)
    {
        if(gondolaSeq[i] != expected && gondolaSeq[i] >= n)
            replacementSeq[gondolaSeq[i] - n - 1] = expected;
        expected ++;
    }
    int val = n;
    int break50 = replacementSeq[len-1];
    int maxxx = break50;
    for (int i = 0; i < len; ++ i)
    {
        val ++;
       // cout << i << " " << val << " -> " << replacementSeq[i] << endl;
       // cout << break50 << endl;
        if(replacementSeq[i] == 0)
        {
            replacementSeq[i] = break50;
            break50 = val;
        }
        else if(replacementSeq[i] == maxxx)
        {
            replacementSeq[i] = break50;
        }
    }
    return len;
}
const long long mod = 1e9 + 9;
long long pow(long long a, long long b)
{
    long long ans = 1, step = a;

    while(b)
    {
        if(b & 1)
        {
            ans *= step;
            ans %= mod;
        }
        step = step * step;
        step %= mod;
        b /= 2;
    }
    return ans;
}
int countReplacement(int n, int inputSeq[])
{
   if(!valid(n, inputSeq))return 0;
    vector < int > g;
    int flag = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(inputSeq[i] > n)g.push_back(inputSeq[i]);
        else flag = 1;
    }
    sort(g.begin(), g.end());
    long long ans = 1;
    if(!flag)
    {
        ans = n;
    }
    int pre = n;

    for (int i = 0; i < g.size(); ++ i)
    {
        long long zeroes = g[i] - pre - 1;
        long long more = g.size() - i;
       // cout << more << " " << zeroes << endl;
        ans *= pow(more, zeroes);
        ans %= mod;
        pre = g[i];
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:24:9: warning: unused variable 'left' [-Wunused-variable]
   24 |     int left = n - cnt;
      |         ^~~~
gondola.cpp:31:9: warning: unused variable 'onpoint' [-Wunused-variable]
   31 |     int onpoint = n+1;
      |         ^~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:69:20: warning: variable 'maxim_place' set but not used [-Wunused-but-set-variable]
   69 |     int maxim = 0, maxim_place = 0;
      |                    ^~~~~~~~~~~
gondola.cpp:121:9: warning: unused variable 'id' [-Wunused-variable]
  121 |     int id = 0;
      |         ^~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:193:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 9 ms 4268 KB Output is correct
7 Correct 6 ms 2652 KB Output is correct
8 Correct 18 ms 5992 KB Output is correct
9 Correct 5 ms 3416 KB Output is correct
10 Correct 22 ms 6492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2484 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 9 ms 4188 KB Output is correct
7 Correct 6 ms 2652 KB Output is correct
8 Correct 19 ms 5860 KB Output is correct
9 Correct 6 ms 3420 KB Output is correct
10 Correct 22 ms 6488 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 12 ms 4208 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 36 ms 6740 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 5 ms 2652 KB Output is correct
12 Correct 6 ms 2908 KB Output is correct
13 Correct 7 ms 2908 KB Output is correct
14 Correct 5 ms 2844 KB Output is correct
15 Correct 11 ms 3676 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2484 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 33 ms 6504 KB Output is correct
10 Correct 30 ms 5900 KB Output is correct
11 Correct 13 ms 3672 KB Output is correct
12 Correct 11 ms 3940 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 37 ms 6448 KB Output is correct
10 Correct 26 ms 5720 KB Output is correct
11 Correct 9 ms 3676 KB Output is correct
12 Correct 11 ms 3932 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 39 ms 8104 KB Output is correct
15 Correct 48 ms 8660 KB Output is correct
16 Correct 7 ms 3672 KB Output is correct
17 Correct 34 ms 6612 KB Output is correct
18 Correct 16 ms 4956 KB Output is correct