oj.uz

Submission #432950

# Submission time Handle Problem Language Result Execution time Memory
432950 2021-06-18T15:33:12 Z REALITYNB Gondola (IOI14_gondola) C++17
100 / 100
 93 ms 5660 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 3e5+1 ;
int b[N];
int valid(int n ,int* a){
    set<int> el ;
    for(int i=0;i<n;i++) el.insert(a[i]) ;
    if(el.size()!=n) return 0 ;
    bool flg= 0 ;
    for(int i=0;i<n;i++){
        if(a[i]>n) continue;
        for(int j=i;j<=n+i;j++){
            if(a[j%n]>n) {b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
                continue ;
            }
            if(a[j%n]==((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n)){
                    b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
                    continue ;
            }
            return 0;
        }
        break ;
    }
    return 1 ;
}
int replacement(int n , int* a , int* ans){
    valid(n,a) ;
    vector<int> hey ;
    for(int i=0;i<n;i++)if(a[i]>n) hey.push_back(i) ;
    if(hey.size()==n){
        for(int i=0;i<n;i++) b[i]=(i+1) ;
    }
    //for(int i=0;i<n;i++) cout << b[i] << " ";
   // cout << endl ;
    sort(hey.begin(),hey.end(),[&](int i ,int j){
        return a[i]>a[j] ;
    }) ;
    int res = 0 ;
    int mx = 0 ;
    for(int i=0;i<n;i++) mx = max(mx,a[i]) ;
   // cout << mx << endl ;
   // for(int x: hey) cout << x << " ";
    //cout << endl ;
    for(int i=n+1;i<=mx;i++){
        if(a[hey.back()]<i){
            hey.pop_back();
        }
        ans[res++]=b[hey.back()];
        b[hey.back()]=i;
    }
    return res;
}
int countReplacement(int n,int* a){
    const int md = 1e9+9 ;
    if(valid(n,a)==0) return 0 ;
    #define int long long
    int spots = 0 ;
    for(int i=0;i<n;i++) spots+=(a[i]>n) ;
    int ans = (spots==n?n:1), mx =  0 ;
    for(int i=0;i<n;i++) mx = max(mx,(int)a[i]) ;
    set<int> vis ;
    for(int i=0;i<n;i++) if(a[i]>n)vis.insert(a[i]) ;
    int last = n;
    function<int(int,int)> be=[](int b ,int e){
        int ans =1;
        while(e){
            if(e&1) ans*=b;
            b*=b,e/=2;
            ans%=md,b%=md ;
        }
        return ans;
    } ;
    //cout << ans << ndl ;
    for(int x: vis)
        (ans*=be(spots,(x-last-1)))%=md,--spots,last = x  ;
       // cout << last << " " << x << " " <<spots << " " << be(spots,(x-last-1)) << endl ;


    #undef int
    int hey = ans ;
    return hey;
}
/*int main(){
    int a[7] = {2, 3, 4, 9, 6, 7, 1} ;
    int ans[10] ;
    int n = replacement(7,a,ans);
    cout << n <<endl ;
    for(int i=0;i<n;i++) cout << ans[i] << " " ;
    return 0 ;
}
*/

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:9:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |     if(el.size()!=n) return 0 ;
      |        ~~~~~~~~~^~~
gondola.cpp:10:10: warning: unused variable 'flg' [-Wunused-variable]
   10 |     bool flg= 0 ;
      |          ^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:31:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     if(hey.size()==n){
      |        ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 14 ms 2300 KB Output is correct
7 Correct 29 ms 3636 KB Output is correct
8 Correct 26 ms 4100 KB Output is correct
9 Correct 8 ms 1484 KB Output is correct
10 Correct 37 ms 4752 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 13 ms 2252 KB Output is correct
7 Correct 30 ms 3544 KB Output is correct
8 Correct 27 ms 4132 KB Output is correct
9 Correct 8 ms 1484 KB Output is correct
10 Correct 35 ms 4804 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 17 ms 2068 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 40 ms 4564 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 292 KB Output is correct
11 Correct 28 ms 5056 KB Output is correct
12 Correct 33 ms 5660 KB Output is correct
13 Correct 33 ms 3048 KB Output is correct
14 Correct 28 ms 4996 KB Output is correct
15 Correct 28 ms 2992 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 71 ms 4248 KB Output is correct
10 Correct 50 ms 3528 KB Output is correct
11 Correct 19 ms 1528 KB Output is correct
12 Correct 19 ms 1804 KB Output is correct
13 Correct 4 ms 632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 69 ms 4308 KB Output is correct
10 Correct 42 ms 3572 KB Output is correct
11 Correct 16 ms 1524 KB Output is correct
12 Correct 22 ms 1772 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 80 ms 4540 KB Output is correct
15 Correct 93 ms 5064 KB Output is correct
16 Correct 12 ms 1196 KB Output is correct
17 Correct 66 ms 3532 KB Output is correct
18 Correct 25 ms 2120 KB Output is correct