結果
問題 | No.2210 equence Squence Seuence |
ユーザー |
|
提出日時 | 2023-02-10 22:14:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,034 ms / 2,000 ms |
コード長 | 6,400 bytes |
コンパイル時間 | 17,345 ms |
コンパイル使用メモリ | 331,616 KB |
最終ジャッジ日時 | 2025-02-10 12:53:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#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 overloadstemplate<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 functionstemplate <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 indexedll 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