#838941 (C++17) No.2210 equence Squence Seuence

• 問題: No.2210 equence Squence Seuence
• ユーザー: Ujjwal Rana
• 提出日時: 2023-02-10 22:14:59
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 803 ms / 2,000 ms
• コード長: 6,400 bytes
• コンパイル時間: 5,238 ms
• コンパイル使用メモリ: 277,276 KB
• 実行使用メモリ: 27,812 KB
• 最終ジャッジ日時: 2024-07-07 16:27:09
• 合計ジャッジ時間: 12,765 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	8 ms; 11,520 KB
testcase_01	AC	8 ms; 11,392 KB
testcase_02	AC	9 ms; 11,392 KB
testcase_03	AC	143 ms; 14,988 KB
testcase_04	AC	170 ms; 15,460 KB
testcase_05	AC	267 ms; 17,524 KB
testcase_06	AC	231 ms; 16,732 KB
testcase_07	AC	643 ms; 24,768 KB
testcase_08	AC	9 ms; 11,520 KB
testcase_09	AC	9 ms; 11,392 KB
testcase_10	AC	9 ms; 11,392 KB
testcase_11	AC	8 ms; 11,516 KB
testcase_12	AC	8 ms; 11,520 KB
testcase_13	AC	803 ms; 27,812 KB
testcase_14	AC	795 ms; 27,812 KB
testcase_15	AC	791 ms; 27,808 KB
testcase_16	AC	790 ms; 27,808 KB
testcase_17	AC	792 ms; 27,808 KB
testcase_18	AC	8 ms; 11,504 KB
testcase_19	AC	8 ms; 11,392 KB
testcase_20	AC	8 ms; 11,444 KB
testcase_21	AC	8 ms; 11,416 KB
testcase_22	AC	7 ms; 11,392 KB
testcase_23	AC	87 ms; 24,912 KB
testcase_24	AC	68 ms; 21,464 KB
testcase_25	AC	78 ms; 23,208 KB
testcase_26	AC	101 ms; 27,328 KB
testcase_27	AC	34 ms; 15,788 KB

ソースコード

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 

#define endl '\n'
typedef long long ll;
#define mod1 (ll)1000000007
#define mod2 (ll)998244353
#define int ll
#define pll pair<ll,ll>
typedef long double lb;
typedef tree<
pair<ll, ll>,
null_type,
less<pair<ll, ll>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
#define eps (lb)(1e-9)
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// Operator overloads
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }

template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
        cin >> it;
    return istream;
}

template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }

// Utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template <typename T, typename... Args>
void print(T &&t, Args &&... args)
{
    cout << t << " ";
    print(forward<Args>(args)...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll p){ // gives random number in [0,p]

 return uniform_int_distribution<ll>(1<<19, p)(rng);
}
int AL = 9;
ll n;
vector<ll>pp((1<<20),0);
vector<ll>v;
template<int... mods>
struct StringHash{
    StringHash(const vector<ll> &s){}
    int hashval(int l1,int r2){
        return 0;
    }
    pll gib(ll l,ll r){
        return {0,0};
    }
    int compare(int l1,int r1,int l2,int r2){
        return true;
    }
};
template<int mod,int... mods>
struct StringHash<mod, mods...>{
    public:
    StringHash(){}
    int modpow(ll x,ll p){
        ll ans = 1;
        while(p){
            if(p&1) ans*=x, ans%=mod;
            x*=x;
            x%=mod;
            p>>=1; 
        }
        return int(ans);
    }
    vector<int> hashvalues;
    vector<int> pows;
    vector<int> invpows;
    StringHash<mods...> ohash;
     
    StringHash(const vector<ll> &s) : ohash(s){
        int n = s.size();
        hashvalues.resize(n+1);
        pows.resize(n+1);
        invpows.resize(n+1);
        pows[0] = 1;
        for(int i=1;i<=n;i++){
            pows[i] = ll(AL + 1) * pows[i-1] % mod;
        }
        invpows[n] = modpow(pows[n], mod-2);
        for(int i=n-1;i>=0;--i){
            invpows[i] = ll(AL + 1) * invpows[i+1] % mod;
        }
        for(int i=1;i<=n;i++){
            hashvalues[i] = (ll(AL + 1) * hashvalues[i-1] + (s[i-1])) % mod;
        }
        // cout<<hashvalues<<"->"<<s<<endl;
    }
    int hashval(int l1,int r1){ // 0 indexed
        ll ans = hashvalues[r1+1] - ll(hashvalues[l1]) * pows[r1-l1+1];
        ans%=mod;
        return ans >= 0 ? ans : ans+mod;
    }
    pll gib(ll l,ll r){
        return {hashval(l,r),ohash.hashval(l,r)};
    }
    pll merge(pll a,pll b){
        pll t=gib(a.first,a.second);
        pll q=gib(b.first,b.second);
        ll len=b.second-b.first+1;
        return { (t.first*pows[len]+q.first)%mod1,(t.second*pp[len]+q.second)%mod2};
    }
    bool compare(int l1,int r1, int l2,int r2){
        return hashval(l1,r1) == hashval(l2, r2) && ohash.compare(l1,r1,l2,r2);
    }
};
pll get(StringHash<mod1,mod2>&s,ll ind,ll k){
    if(k<ind){
        return s.gib(0,k);
    }
    else if(ind==0){
        return s.gib(1,k+1);
    }
    else{
        return s.merge({0,ind-1},{ind+1,k+1});
    }
}
ll okgib(ll a,ll k){
    if(k<a){return v[k];}
    return v[k+1];
}
bool comp(ll a,ll b,StringHash<mod1,mod2>&s){
    if(a==b){return 0;}
    if(get(s,a,n-2)==get(s,b,n-2)){return 0;}
    ll lo=0,hi=n-2,ans=hi;
    while (lo<=hi)
    {
       ll mid=(lo+hi)>>1;
       if(get(s,a,mid)!=get(s,b,mid)){ans=mid; hi=mid-1;}
       else{lo=mid+1;}
    }
    return okgib(a,ans)<okgib(b,ans);
    
}
class Solution {
public:
    
    void merge(vector<int>& nums,int l, int r, int m,StringHash<mod1,mod2>&s){
        int n=nums.size();
        vector<int> ans(r-l+1);
        int i=l,j=m+1,k=0;
        while(i<=m && j<=r){
            if(comp(nums[i],nums[j],s)){
                ans[k++]=nums[i++];
            }
            else{
                ans[k++]=nums[j++];
            }
        }
        while(i<=m){
            ans[k++]=nums[i++];
        }
        while(j<=r){
            ans[k++]=nums[j++];
        }
        for(int i=0;i<=r-l;i++){
            nums[l+i]=ans[i];
        }
    }
    void mergesort(vector<int>& nums,int l,int r,StringHash<mod1,mod2>&s){
        if(l>=r){
            return ;
        }
       int m=l+(r-l)/2;
        mergesort(nums,l,m,s);
        mergesort(nums,m+1,r,s);
        merge(nums,l,r,m,s);
    }
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        auto s=StringHash<mod1,mod2>(v);
        // cout<<v<<endl;
        mergesort(nums,0,n-1,s);
        return nums;
    }
};
void solve();
signed main() {
io;
ll t=1,n=1;
// cin>>t;
while (t--){
     solve();
    }
     return 0;
}
void solve(){
     ll n,k;
     cin>>n>>k;
     k--;
     vector<ll>v(n);
     cin>>v;
    ::v=v;
    ::n=n;
    vector<ll>p;
    for(ll i(0);i<n;++i){
        p.push_back(i);
    }
    pp[0]=1;
    for(int i(1);i<pp.size();++i){
        pp[i]=(AL+1)*pp[i-1];
        pp[i]%=mod2;
    }
    Solution ss;
    ss.sortArray(p);
    // cout<<p<<endl;
    ll j=p[k];
    v.erase(begin(v)+j);
    cout<<v<<endl;
     
     



}
// Do not get stuck on a single approach for long, think of multiple ways