結果

問題 No.2210 equence Squence Seuence
ユーザー Ujjwal RanaUjjwal Rana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0