QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207110 | #7522. Sequence Shift | c20231020 | WA | 13ms | 13472kb | C++23 | 8.7kb | 2023-10-08 09:32:47 | 2023-10-08 09:32:47 |
Judging History
answer
/*
膜拜传奇特级宗师 Afterglow 大神儿
今天在 florr 首页称您为大夏尊贵的大名儿
一股敬佩之情油生然而
您在 florr 为国争光,扬我大夏威名
向您献上最真挚的膜拜!!!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
*/
/*
_____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \
/ \ \ / \ \ / \____\ / \ \
\ \ \ / \ \ / / / \ \ \
\ \ \ / \ \ / / / \ \ \
\ \ \ / /\ \ \ / /____/ \ \ \
\ \ \ / / \ \ \ / | | \ \ \
\ \ \ / / \ \ \ / | | \ \ \
\ \ \ / / / \ \ \ / | | \ \ \
\ \ \ / / / \ \ \ / |____|__ _____ \ \ \
_______________\ \____\/ /____/ \ \ \ / /| \ \ _______________\ \____\
\ / /\ \ \ \ \ \\ / | _________\____\\ / /
\ ____________/____/ \ \ \ \ \____\\/__| | | \ ____________/____/
\ \ \ \ \ \ | | | | | | \ \ \
\ \ \ \ \ \ | | | | | | \ \ \
\ \ \ \ \ \ | |____| | | | \ \ \
\ \ \ \ \ \ / / / \ | | \ \ \
\ \ \ \ \ \/ / / \ | | \ \ \
\ \____\ \ \___/ / / \ | | \ \____\
\ / / \ / / \| | \ / /
\/____/ \_______/____/ \____| \/____/
*/
#define poj
#define zcz
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
//C++11
#if __cplusplus>=201103L
#include<chrono>
#include<random>
#include<unordered_set>
#include<unordered_map>
#endif
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
private:
#ifdef poj
static const int MAXBF=1<<20;
#else
const int MAXBF=1<<27;
#endif
FILE *inf;
char *inbuf,*inst,*ined;
inline char _getchar(){
if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
return inst==ined?EOF:*inst++;
}
public:
fastin(FILE*_inf=stdin){
inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
}
~fastin(){delete[]inbuf;}
template<typename Int> fastin&operator>>(Int &n){
static char c;
Int t=1;
while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
n=(c^48);
while((c=_getchar())>='0'&&c<='9')n=n*10+(c^48);
n*=t;
return *this;
}
fastin&operator>>(char&c){
while((c=_getchar())<'!'||c>'~');
return *this;
}
fastin&operator>>(char*s){
int t=0;
static char c;
while((c=_getchar())==' '||c=='\n');
s[t++]=c;
while((c=_getchar())>='!'&&c<='~')s[t++]=c;
s[t]='\0';
return *this;
}
}fi;
class fastout{
private:
#ifdef poj
static const int MAXBF=1<<20;
#else
const int MAXBF=1<<27;
#endif
FILE *ouf;
char *oubuf,*oust,*oued;
inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
inline void _putchar(char c){
if(oued==oust+MAXBF)_flush(),oued=oubuf;
*oued++=c;
#ifdef local
_flush();
#endif
}
public:
fastout(FILE*_ouf=stdout){
oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
}
~fastout(){_flush();delete[]oubuf;}
template<typename Int> fastout&operator<<(Int n){
if(n<0)_putchar('-'),n=-n;
static char S[20];
int t=0;
do{S[t++]='0'+n%10,n/=10;}while(n);
for(int i=0;i<t;++i)_putchar(S[t-i-1]);
return *this;
}
fastout&operator<<(char c){_putchar(c);return *this;}
fastout&operator<<(char*s){
for(int i=0;s[i];++i)_putchar(s[i]);
return *this;
}
fastout&operator<<(const char*s){
for(int i=0;s[i];++i)_putchar(s[i]);
return *this;
}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod7 1000000007
#define mod9 998244353
#define ll long long
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define fr first
#define sc second
#define next ___
#define pb push_back
#define N 2000010
#define M 5000010
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b,c) for(ll i=(a);i<=(b);i+=c)
#define Per(i,a,b,c) for(ll i=(a);i>=(b);i-=c)
#define Gra(i) for(ll i=h[x];i;i=next[i])
typedef int arr[N];
typedef int arm[M];
typedef ll arl[N];
typedef ll alm[M];
typedef double ard[N];
typedef double adm[M];
namespace modint{
template<typename Int,Int mod,Int m1>
struct modint{
Int v;
modint(){v=0;}
modint(Int a){v=a;}
bool operator==(modint a){return v==a.v;}
bool operator!=(modint a){return v!=a.v;}
bool operator<(modint a){return v<a.v;}
bool operator>(modint a){return v>a.v;}
bool operator<=(modint a){return v<=a.v;}
bool operator>=(modint a){return v>=a.v;}
bool operator==(Int a){return v==a;}
bool operator!=(Int a){return v!=a;}
bool operator<(Int a){return v<a;}
bool operator>(Int a){return v>a;}
bool operator<=(Int a){return v<=a;}
bool operator>=(Int a){return v>=a;}
friend bool operator==(Int a,modint b){return b==a;}
friend bool operator!=(Int a,modint b){return b!=a;}
friend bool operator<(Int a,modint b){return b>a;}
friend bool operator>(Int a,modint b){return b<a;}
friend bool operator<=(Int a,modint b){return b>=a;}
friend bool operator>=(Int a,modint b){return b<=a;}
modint operator+(modint a){return v>=mod-a.v?v-mod+a.v:v+a.v;}
modint operator-(modint a){return v>=a.v?v-a.v:v+mod-a.v;}
modint modnum(modint a){
return a-((__int128(a.v)*m1)>>80)*mod;
}
modint operator*(modint a){return modnum(v*a.v);}
modint operator+=(modint a){*this=*this+a;return *this;}
modint operator-=(modint a){*this=*this-a;return *this;}
modint operator*=(modint a){*this=*this*a;return *this;}
modint qpow(modint a,Int b){
modint r(1);
for(;b;b>>=1,a*=a)if(b&1)r*=a;
return r;
}
modint operator/(modint a){return qpow(a,mod-2)*v;}
modint operator/=(modint a){*this=*this/a;return *this;}
modint&operator++(){*this=*this+1;return *this;}
modint&operator--(){*this=*this-1;return *this;}
const modint operator++(int){modint r=*this;++*this;return r;}
const modint operator--(int){modint r=*this;--*this;return r;}
friend modint operator+(Int a,modint b){return b+a;}
friend modint operator-(Int a,modint b){return b-a;}
friend modint operator*(Int a,modint b){return b*a;}
friend modint operator/(Int a,modint b){return modint(a)/b;}
#ifdef cout
friend fastin&operator>>(fastin&in,modint&n){in>>n.v;return in;}
friend fastout&operator<<(fastout&out,modint n){out<<n.v;return out;}
#else
friend istream&operator>>(istream&in,modint&n){in>>n.v;return in;}
friend ostream&operator<<(ostream&out,modint n){out<<n.v;return out;}
#endif
};
typedef modint<long long,1000000007,1208925811152148> int7;
typedef modint<long long,998244353,1211051999424262> int9;
}
using namespace modint;
int n,m,q,a[N],b[N],ans[N],k,l;
pii t[N];
void solve(){
cin>>n>>q;
m=n+q;
For(i,1,n){
cin>>a[i];
t[i]={a[i],i};
};
sort(t+1,t+1+n,greater<pii>());
k=max(1,min(n,(int)(1.0*n/(n+m)*sqrt(n*2*log2(1.0*n*q/m)))));
l=t[k].fr+1e9*(m-k+1)/m;
For(i,1,m){
cin>>b[i];
if(i>n)b[i]^=ans[i-1];
For(j,1,n){
int v=t[j].fr+b[i];
if(v<l)break;
int x=i+n-t[i].sc;
if(x>=n&&x<=m)ans[x]=max(ans[x],v);
};
if(i>=n){
if(ans[i])cout<<ans[i]<<'\n';
else{
int v=0;
For(j,1,n)v=max(v,a[j]+b[i+j-n]);
cout<<(ans[i]=v)<<'\n';
}
}
};
return;
}
int main(){
#ifndef zcz
czc;
#endif
int t=1;
while(t--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9996kb
input:
5 3 1 4 3 2 5 7 5 8 3 2 3 6 4
output:
11 13 16 25
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 10056kb
input:
1 0 103509429 823330096
output:
926839525
result:
ok single line: '926839525'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9860kb
input:
1 1 576560149 691846236 1156187222
output:
1268406385 835582012
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 9924kb
input:
1 10 700282491 332230980 90825676 1630266999 644973380 262379760 2122877054 1851957134 1370195232 110993724 1319359505 1883523208
output:
1032513471 1654684398 759763732 888538827 1695749302 1163465539 1425605448 789576931 1397740634 1202288326 1638577353
result:
ok 11 lines
Test #5:
score: 0
Accepted
time: 12ms
memory: 13472kb
input:
1000 100000 438001359 929744877 710148392 323984311 727016267 323629255 495752276 309120511 312675195 717795522 937464489 624952229 444774478 829169766 707441777 609125148 25459976 849166512 716162953 882416779 189669312 135698832 632796131 592794700 569746403 231058028 389412868 824283503 801480367...
output:
1962871590 1986083253 1967509108 1973351244 1974354421 1956371849 1976394149 1995721753 1946870160 1984280254 1961237540 1955903880 1944520591 1937726835 1993563403 1927000559 1951483558 1979133252 1979156812 1941301401 1922284543 1980597785 1963663583 1946961524 1933606347 1953947075 1953071855 194...
result:
ok 100001 lines
Test #6:
score: -100
Wrong Answer
time: 13ms
memory: 9908kb
input:
10000 10000 760845880 236665988 765352292 817854026 789863420 399953246 270535243 932350041 48814223 670950468 456660682 416165008 999681497 666880584 56581573 134567049 403285848 144814129 973325555 23519957 518449311 738687225 345716065 2309498 477743569 555951695 911860717 920761968 569179690 349...
output:
1990514380 1974843876 1992500750 1994731468 1983411218 1986646709 1979643361 1990060423 1988174297 1983373232 1995134632 1989936349 1993187026 1988927807 1971595730 1988272839 1990590966 1981928791 1987819156 1987483957 1979800700 1986611531 1973877196 1995735988 1985734454 1987573480 1988935268 199...
result:
wrong answer 66th lines differ - expected: '1996582121', found: '1982919512'