oj.uz

Submission #292147

# Submission time Handle Problem Language Result Execution time Memory
292147 2020-09-06T12:50:12 Z mat_v Gondola (IOI14_gondola) C++14
100 / 100
 40 ms 2520 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 1000000009
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int tmp[250005];

int valid(int n, int inputSeq[])
{
    vector<int> svi;
    ff(i,0,n - 1)svi.pb(inputSeq[i]);
    sort(svi.begin(), svi.end());
    ff(i,0,n - 2)if(svi[i] == svi[i + 1])return 0;

    int gde = -1;
    ff(i,0,n - 1){
        if(inputSeq[i] <= n){
            gde = i;
            break;
        }
    }
    if(gde == -1)return 1;
    ff(i,gde,gde+n-1){
        tmp[i%n] = inputSeq[gde] + i - gde;
        if(tmp[i%n] > n)tmp[i%n] -= n;
    }
    ff(i,0,n - 1){
        if(inputSeq[i] <= n && inputSeq[i] != tmp[i])return 0;
    }
    return 1;
}

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

int niz[250005];
bool use[250005];
int poz[250005];

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    ff(i,0,n - 1)niz[i] = gondolaSeq[i];
    int gde = 0;
    int val = 1;
    ff(i,0,n - 1){
        if(niz[i] <= n){
            gde = i;
            val = niz[i];
            break;
        }
    }
    ff(i,gde,gde+n-1){
        tmp[i%n] = val + i - gde;
        if(tmp[i%n] > n)tmp[i%n] -= n;
    }
    //ff(i,0,n - 1)cout << tmp[i] << " ";
    int tr = n+1;
    priority_queue<pii>pq;
    ff(i,0,n - 1){
        if(niz[i] > n){
            pq.push({-niz[i], i});
        }
    }
    vector<int> sol;
    while(!pq.empty()){
        pii sta = pq.top();
        pq.pop();
        int koji = sta.yy;
        int broj = -sta.xx;
        while(tr <= broj){
            sol.pb(tmp[koji]);
            tmp[koji] = tr;
            tr++;
        }
    }
    int m = sol.size();
    ff(i,0,m - 1){
        replacementSeq[i] = sol[i];
    }
    return m;
}

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

ll add(ll x, ll y){
    return (x + y) % mod;
}
ll mul(ll x, ll y){
    return (x * y) % mod;
}
ll power(ll x, ll y){
    if(y == 0)return 1;
    ll pola = power(x, y/2);
    pola = mul(pola, pola);
    if(y%2 == 1)pola = mul(pola, x);
    return pola;
}


int countReplacement(int n, int inputSeq[]){
    if(valid(n, inputSeq) == 0)return 0;
    sort(inputSeq, inputSeq + n);
    ll pom = 1;
    pom = n;
    ff(i,0,n - 1)if(inputSeq[i] <= n)pom = 1;
    int tr = n+1;
    ll ans = 1;
    int poc = 0;
    while(poc < n && inputSeq[poc] <= n)poc++;
    ff(i,poc,n - 1){
        ll kol = n - i;
        ll raz = inputSeq[i] - tr;
        ans = mul(ans, power(kol, raz));
        tr = inputSeq[i] + 1;
    }
    ans = mul(ans, pom);
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:28:5: note: in expansion of macro 'ff'
   28 |     ff(i,0,n - 1)svi.pb(inputSeq[i]);
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:30:5: note: in expansion of macro 'ff'
   30 |     ff(i,0,n - 2)if(svi[i] == svi[i + 1])return 0;
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:33:5: note: in expansion of macro 'ff'
   33 |     ff(i,0,n - 1){
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:40:5: note: in expansion of macro 'ff'
   40 |     ff(i,gde,gde+n-1){
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:44:5: note: in expansion of macro 'ff'
   44 |     ff(i,0,n - 1){
      |     ^~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:58:5: note: in expansion of macro 'ff'
   58 |     ff(i,0,n - 1)niz[i] = gondolaSeq[i];
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:61:5: note: in expansion of macro 'ff'
   61 |     ff(i,0,n - 1){
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:68:5: note: in expansion of macro 'ff'
   68 |     ff(i,gde,gde+n-1){
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:75:5: note: in expansion of macro 'ff'
   75 |     ff(i,0,n - 1){
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:93:5: note: in expansion of macro 'ff'
   93 |     ff(i,0,m - 1){
      |     ^~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:121:5: note: in expansion of macro 'ff'
  121 |     ff(i,0,n - 1)if(inputSeq[i] <= n)pom = 1;
      |     ^~
gondola.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
gondola.cpp:126:5: note: in expansion of macro 'ff'
  126 |     ff(i,poc,n - 1){
      |     ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 10 ms 1148 KB Output is correct
7 Correct 21 ms 1780 KB Output is correct
8 Correct 16 ms 1660 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 22 ms 1920 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct
7 Correct 20 ms 1788 KB Output is correct
8 Correct 15 ms 1660 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 25 ms 1984 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 10 ms 1152 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 23 ms 2032 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 13 ms 1664 KB Output is correct
12 Correct 15 ms 1920 KB Output is correct
13 Correct 21 ms 1912 KB Output is correct
14 Correct 14 ms 1664 KB Output is correct
15 Correct 27 ms 2520 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 28 ms 1788 KB Output is correct
10 Correct 21 ms 1532 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Correct 10 ms 1024 KB Output is correct
13 Correct 3 ms 512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 26 ms 1788 KB Output is correct
10 Correct 21 ms 1532 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 10 ms 1024 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 34 ms 2164 KB Output is correct
15 Correct 40 ms 2292 KB Output is correct
16 Correct 7 ms 768 KB Output is correct
17 Correct 24 ms 1536 KB Output is correct
18 Correct 16 ms 1256 KB Output is correct