제출 #1333059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333059		aaaaaaaa	Money (IZhO17_money)	C++20	0 / 100	1595 ms	344 KiB

money

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int H = 20;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct sub_hash {

    vector<vector<int>> dp, inv;

    int mod[H] = {
        1000000007,1000000009,998244353,1000000033,1000000087,
        1000000093,1000000097,1000000103,1000000123,1000000181,
        1000000207,1000000223,1000000241,1000000271,1000000289,
        1000000297,rnd(),1000000349,rnd(),1000000403
    };

    int base[H] = {
        31,rnd(),41,43,47,
        53,59,61,rnd(),71,
        73,79,83,89,97,
        101,rnd(),107,109,113
    };

    int pw(long long a,long long b,int m){
        long long r=1;
        while(b){
            if(b&1) r=r*a%m;
            a=a*a%m;
            b>>=1;
        }
        return r;
    }

    tuple<
        int,int,int,int,int,int,int,int,int,int,
        int,int,int,int,int,int,int,int,int,int
    > query(int l,int r){

        int res[H];

        for(int k=0;k<H;k++){
            long long val=(dp[k][r+1]-dp[k][l]+mod[k])%mod[k];
            val=val*inv[k][l]%mod[k];
            res[k]=val;
        }

        return make_tuple(
            res[0],res[1],res[2],res[3],res[4],
            res[5],res[6],res[7],res[8],res[9],
            res[10],res[11],res[12],res[13],res[14],
            res[15],res[16],res[17],res[18],res[19]
        );
    }

    void init(const vector<int>& vec){

        int n = vec.size();

        dp.assign(H, vector<int>(n+5));
        inv.assign(H, vector<int>(n+5));

        for(int k=0;k<H;k++){

            long long p = base[k];
            long long pwv = 1;

            for(int i=0;i<n;i++){
                dp[k][i+1]=(dp[k][i]+(vec[i]-'0'+1)*pwv)%mod[k];
                pwv=pwv*p%mod[k];
            }

            inv[k][n-1]=pw(pw(p,n-1,mod[k]),mod[k]-2,mod[k]);

            for(int i=n-2;i>=0;i--)
                inv[k][i]=1LL*inv[k][i+1]*p%mod[k];
        }
    }
} hsh_on, hsh_srt;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, ans = 0;
    cin >> n;

    vector<int> a(n, 0), srt(n, 0);

    for(int i = 0; i < n; ++i){
        cin >> a[i];
        srt[i] = a[i];
    }



    sort(srt.begin(), srt.end());



    int remov = 0;

    while(remov != n){
        hsh_on.init(a);
        hsh_srt.init(srt);

        map<tuple<int,int,int,int,int,int,int,int,int,int,
        int,int,int,int,int,int,int,int,int,int>, pair<int, int>> mp;

        for(int i = 0; i < (int) srt.size(); ++i){
            for(int j = i; j < (int) srt.size(); ++j){
                mp[hsh_srt.query(i, j)] = {i, j};
            }
        }

        int i = (int) a.size() - 1, j = (int) a.size() - 1;
        int st = 0, en = (int) a.size() - 1;

        pair<int, int> rem;

        while(st <= en){
            int mid = st + (en - st) / 2;
            tuple<int,int,int,int,int,int,int,int,int,int,
        int,int,int,int,int,int,int,int,int,int> qry = hsh_on.query(mid, (int) a.size() - 1);
            if(mp.count(qry)){
                j = mid;
                en = mid - 1;
                rem = mp[qry];
            }else{
                st = mid + 1;
            }
        }

        vector<int> new_arr;

        for(int i = 0; i < rem.first; ++i){
            new_arr.push_back(srt[i]);
        }

        for(int i = rem.second + 1; i < (int) a.size(); ++i){
            new_arr.push_back(srt[i]);
        }

        ans += 1, remov += rem.second - rem.first + 1;

        int k = rem.second - rem.first + 1;

        while(k--){
            a.pop_back();
        }

        swap(new_arr, srt);
    }

    cout << ans << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

money.cpp:18:23: warning: narrowing conversion of 'rnd.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   18 |         1000000297,rnd(),1000000349,rnd(),1000000403
      |                    ~~~^~
money.cpp:18:40: warning: narrowing conversion of 'rnd.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   18 |         1000000297,rnd(),1000000349,rnd(),1000000403
      |                                     ~~~^~
money.cpp:22:15: warning: narrowing conversion of 'rnd.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   22 |         31,rnd(),41,43,47,
      |            ~~~^~
money.cpp:23:21: warning: narrowing conversion of 'rnd.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |         53,59,61,rnd(),71,
      |                  ~~~^~
money.cpp:25:16: warning: narrowing conversion of 'rnd.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   25 |         101,rnd(),107,109,113
      |             ~~~^~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55