oj.uz

Submission #1018372

# Submission time Handle Problem Language Result Execution time Memory
1018372 2024-07-09T20:45:52 Z n3rm1n Gondola (IOI14_gondola) C++17
75 / 100
 37 ms 6992 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;
    for (int i = 0; i < n; ++ i)
    {
        if(inputSeq[i] > n)g.push_back(inputSeq[i]);
    }
    sort(g.begin(), g.end());
    int pre = n;
    long long ans = 1;
    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:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 0 ms 2396 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 17 ms 5980 KB Output is correct
9 Correct 6 ms 3416 KB Output is correct
10 Correct 22 ms 6424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 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 17 ms 5976 KB Output is correct
9 Correct 6 ms 3420 KB Output is correct
10 Correct 22 ms 6492 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 14 ms 4188 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 31 ms 6632 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 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 1 ms 2652 KB Output is correct

Subtask #5
10.0 / 10.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 0 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 0 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2620 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 1 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 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 7 ms 2652 KB Output is correct
12 Correct 6 ms 2908 KB Output is correct
13 Correct 8 ms 2908 KB Output is correct
14 Correct 5 ms 2652 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 1 ms 2392 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2488 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 37 ms 6992 KB Output is correct
10 Correct 24 ms 6232 KB Output is correct
11 Correct 12 ms 3676 KB Output is correct
12 Correct 11 ms 4188 KB Output is correct
13 Incorrect 3 ms 2908 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2392 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 0 ms 2496 KB Output is correct
9 Correct 31 ms 6872 KB Output is correct
10 Correct 23 ms 6232 KB Output is correct
11 Correct 10 ms 3844 KB Output is correct
12 Correct 11 ms 4020 KB Output is correct
13 Incorrect 3 ms 2908 KB Output isn't correct
14 Halted 0 ms 0 KB -