oj.uz

Submission #974362

# Submission time Handle Problem Language Result Execution time Memory
974362 2024-05-03T09:15:53 Z rahidilbayramli Gondola (IOI14_gondola) C++17
100 / 100
 46 ms 7108 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll mod = 1e9+9;
ll binpow(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

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

int valid(int n, int inputSeq[])
{
    int nxt[n+5], v[n+5];
    set<int>st;
    for(int i = 1; i <= n; i++)
    {
        v[i] = inputSeq[i-1];
        st.insert(v[i]);
    }
    for(int i = 1; i <= n; i++)
        nxt[i] = (i % n) + 1;
    bool flag = false;
    for(int i = 1; i <= n; i++)
    {
        if(v[i] <= n && v[(i%n)+1] <= n && nxt[v[i]] != v[(i%n)+1])
            flag = true;
    }
    if(flag || st.size() < n)
        return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int v[n+5];
    int flag = 0;
    for(int i = 1; i <= n; i++){
        v[i] = gondolaSeq[i-1];
        if(v[i] <= n)
            flag = 1;
    }
    if(!flag)
    {
        vector<pii>vect;
        for(int i = 1; i <= n; i++)
            vect.pb({v[i], i});
        sort(all(vect));
        int last = n + 1, idx = 0;
        for(int i = 0; i < n; i++)
        {
            replacementSeq[idx] = vect[i].s;
            idx++;
            for(int j = last; j < vect[i].f; j++)
            {
                replacementSeq[idx] = j;
                idx++;
            }
            last = vect[i].f + 1;
        }
        return idx;
    }
    else
    {
        vector<pii>vect;
        int idx;
        for(int i = 1; i <= n; i++)
        {
            if(v[i] <= n && v[i] >= 1){
                idx = i;
                break;
            }
        }
        vect.pb({v[idx], v[idx]});
        int idxt = v[idx];
        for(int i = idx + 1; i <= n; i++)
        {
            idxt++;
            if(idxt == n + 1)
                idxt = 1;
            vect.pb({v[i], idxt});
        }
        idxt = v[idx];
        for(int i = idx - 1; i >= 1; i--)
        {
            idxt--;
            if(idxt == 0)
                idxt = n;
            vect.pb({v[i], idxt});
        }
        sort(all(vect));
        int last = n + 1;
        idx = 0;
        for(int i = 0; i < n; i++)
        {
            if(vect[i].f > n){
                replacementSeq[idx] = vect[i].s;
                idx++;
            }
            for(int j = last; j < vect[i].f; j++)
            {
                replacementSeq[idx] = j;
                idx++;
            }
            last = max(last, vect[i].f + 1);
        }
        return idx;
    }
}

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

int countReplacement(int n, int inputSeq[])
{
    int k = valid(n, inputSeq);
    if(k == 0)
        return 0;
    else
    {
        ll v[n+5], cnt = 0;
        bool flag1 = false, flag2 = false;
        vl vect;
        for(ll i = 1; i <= n; i++)
            v[i] = inputSeq[i-1];
        for(ll i = 1; i <= n; i++)
        {
            if(v[i] > n)
            {
                vect.pb(v[i]);
                flag1 = true;
                cnt++;
            }
            if(v[i] <= n)
                flag2 = true;
        }
        ll h = 1;
        if(!flag2)
            h = n;
        sort(all(vect));
        ll lst = n + 1;
        for(ll i = 0; i < vect.size(); i++)
        {
            ll diff = vect[i] - lst;
            ll p = binpow(cnt, diff);
            h *= p;
            h %= mod;
            cnt--;
            lst = vect[i] + 1;
        }
        int f = h;
        return f;
    }
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     if(flag || st.size() < n)
      |                ~~~~~~~~~~^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:165:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(ll i = 0; i < vect.size(); i++)
      |                       ~~^~~~~~~~~~~~~
gondola.cpp:145:14: warning: variable 'flag1' set but not used [-Wunused-but-set-variable]
  145 |         bool flag1 = false, flag2 = false;
      |              ^~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:108:17: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |         for(int i = idx - 1; i >= 1; i--)
      |                 ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 2652 KB Output is correct
7 Correct 25 ms 4468 KB Output is correct
8 Correct 18 ms 4576 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 20 ms 5212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 22 ms 4336 KB Output is correct
8 Correct 18 ms 4632 KB Output is correct
9 Correct 7 ms 1624 KB Output is correct
10 Correct 23 ms 5208 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 380 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 26 ms 5468 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 10 ms 2008 KB Output is correct
12 Correct 12 ms 2260 KB Output is correct
13 Correct 12 ms 1496 KB Output is correct
14 Correct 10 ms 2004 KB Output is correct
15 Correct 16 ms 2448 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 32 ms 5328 KB Output is correct
10 Correct 22 ms 4184 KB Output is correct
11 Correct 8 ms 1880 KB Output is correct
12 Correct 9 ms 2136 KB Output is correct
13 Correct 2 ms 856 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 27 ms 5168 KB Output is correct
10 Correct 22 ms 4180 KB Output is correct
11 Correct 8 ms 1884 KB Output is correct
12 Correct 10 ms 1992 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 33 ms 5980 KB Output is correct
15 Correct 46 ms 7108 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 24 ms 4784 KB Output is correct
18 Correct 13 ms 3164 KB Output is correct