QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194434 | #7522. Sequence Shift | ucup-team191# | WA | 19ms | 9764kb | C++23 | 4.3kb | 2023-09-30 20:42:28 | 2023-09-30 20:42:29 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcountll
#define all(a) begin(a),end(a)
//for kactl
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
cout<<w.size()<<en;
for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
if (w.size()) cout<<w[w.size()-1]<<en;
if (fl) cout<<flush;
}
void M998()
{
swap(MOD,MOD2);
}
ll raand()
{
ll a=rund();
a*=RAND_MAX;
a+=rund();
return a;
}
#define rand raand
ll raaand()
{
return raand()*(MOD-7)+raand();
}
template<class T>
vi compress(vector<T>&v)
{
set<T> s;
for (auto a: v) s.insert(a);
vector<T> o(all(s));
vi nv;
for (int i=0;i<(int)v.size();++i) nv.pb(lower_bound(all(o),v[i])-o.begin());
return nv;
}
string to_upper(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
return a;
}
string to_lower(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
return a;
}
ll sti(string a,int base=10)
{
ll k=0;
for (int i=0;i<(int)a.size();++i)
{
k*=base;
k+=a[i]-'0';
}
return k;
}
template<class T>
void eras(vector<T>& a,T b)
{
a.erase(find(a.begin(),a.end(),b));
}
string its(ll k,int base=10)
{
if (k==0) return "0";
string a;
while (k)
{
a.push_back((k%base)+'0');
k/=base;
}
reverse(a.begin(),a.end());
return a;
}
ll min(ll a,int b)
{
if (a<b) return a;
return b;
}
ll min(int a,ll b)
{
if (a<b) return a;
return b;
}
ll max(ll a,int b)
{
if (a>b) return a;
return b;
}
ll max(int a,ll b)
{
if (a>b) return a;
return b;
}
ll gcd(ll a,ll b)
{
if (b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
template<class T,class K>
pair<T,K> mp(T a,K b)
{
return make_pair(a,b);
}
inline int mult(ll a,ll b)
{
return (a*b)%MOD;
}
inline int pot(int n,int k)
{
if (k==0) return 1;
ll a=pot(n,k/2);
a=mult(a,a);
if (k%2) return mult(a,n);
else return a;
}
int divide(int a,int b)
{
return mult(a,pot(b,MOD-2));
}
inline int sub(int a,int b)
{
if (a-b>=0) return a-b;
return a-b+MOD;
}
inline int add(int a,int b)
{
if (a+b>=MOD) return a+b-MOD;
return a+b;
}
void ad(int&a,int b)
{
a+=b;
if (a>=MOD) a-=MOD;
}
void su(int&a,int b)
{
a-=b;
if (a<0) a+=MOD;
}
bool prime(ll a)
{
if (a==1) return 0;
for (int i=2;i<=round(sqrt(a));++i)
{
if (a%i==0) return 0;
}
return 1;
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
const int N=2000010,K=10;
int q,n,a[N],b[N],an[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
cin>>n>>q;
for (int i=0;i<n;++i) cin>>a[i];
for (int i=0;i<n;++i) cin>>b[i];
if (n*q<=1e8)
{
int ma=0;
for (int i=0;i<n;++i) ma=max(ma,a[i]+b[i]);
cout<<ma<<en;
for (int i=n;i<n+q;++i)
{
int w;
cin>>w;
w^=ma;
b[i]=w;
ma=0;
for (int j=0;j<n;++j) ma=max(ma,a[j]+b[j+(i-n+1)]);
cout<<ma<<en;
}
}
else
{
vi dob;
const int POT=MOD-MOD/K/sqrt(n);
for (int i=0;i<n;++i) if (a[i]>=POT) dob.pb(i);
for (int i=0;i<n;++i) if (b[i]>=POT)
{
for (auto x: dob) if (x<=i) an[i-x]=max(an[i-x],a[x]+b[i]);
}
cout<<an[0]<<en;
for (int i=1;i<=q;++i)
{
int w;
cin>>w;
w^=an[i-1];
if (w>=POT) for (auto x: dob) an[i+(n-1)-x]=max(an[i+(n-1)-x],a[x]+w);
cout<<an[i]<<en;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7892kb
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: 1ms
memory: 7844kb
input:
1 0 103509429 823330096
output:
926839525
result:
ok single line: '926839525'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
1 1 576560149 691846236 1156187222
output:
1268406385 835582012
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 7728kb
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: 19ms
memory: 9764kb
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: 0
Accepted
time: 13ms
memory: 7804kb
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:
ok 10001 lines
Test #7:
score: -100
Wrong Answer
time: 15ms
memory: 8156kb
input:
10000 100000 682604470 430466819 955519058 186918998 587587373 201134122 473675328 586747694 132807628 255672373 504315038 137082392 753499284 586570202 133549919 570424589 87103369 2142325 895908281 852456682 239920694 443878018 717067433 437134318 39426086 82137124 698018668 518394430 430778732 56...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1984544998', found: '0'