QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#494883 | #9141. Array Spread | PhantomThreshold# | WA | 38ms | 3836kb | C++20 | 2.9kb | 2024-07-27 17:27:35 | 2024-07-27 17:27:36 |
Judging History
你现在查看的是最新测评结果
- [2024-09-18 18:58:44]
- hack成功,自动添加数据
- (/hack/840)
- [2024-09-18 18:53:02]
- hack成功,自动添加数据
- (/hack/839)
- [2024-07-29 03:53:23]
- hack成功,自动添加数据
- (/hack/753)
- [2024-07-29 03:51:16]
- hack成功,自动添加数据
- (/hack/752)
- [2024-07-29 03:50:24]
- hack成功,自动添加数据
- (/hack/751)
- [2024-07-29 03:48:52]
- hack成功,自动添加数据
- (/hack/750)
- [2024-07-27 17:27:35]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<int> L(m+5),R(m+5);
map<int,int> mp;
for(int i=1;i<=m;i++)
{
cin>>L[i]>>R[i];
mp[L[i]]=mp[R[i]+1]=0;
}
int idx=0;
for(auto &[x,y]:mp)
{
y=++idx;
}
for(int i=1;i<=m;i++)
{
L[i]=mp[L[i]];
R[i]=mp[R[i]+1];
}
//[li,ri)
auto check=[&](int P,int Q)
{
vector<vector<pair<int,int>>> G(idx+5);
for(int i=1;i<=m;i++)
{
// cerr<<L[i]<<' '<<R[i]<<endl;
G[L[i]].emplace_back(R[i],P);
// cerr<<R[i]<<' '<<L[i]<<endl;
G[R[i]].emplace_back(L[i],-Q);
}
for(int i=1;i<idx;i++)
{
// cerr<<i+1<<' '<<i<<endl;
G[i+1].emplace_back(i,0);
}
vector<long long> dis(idx+5),cnt(idx+5),inq(idx+5);
queue<int> q;
for(int i=1;i<=idx;i++)
{
q.push(i);
}
while(not q.empty())
{
int u=q.front();q.pop();
inq[u]=0;
for(auto [v,w]:G[u])
{
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(not inq[v])
{
cnt[v]++;
if(cnt[v]>idx)return false;
inq[v]=1;
q.push(v);
}
}
}
}
return true;
};
/*
for(int i=1;i<=5;i++)
for(int j=1;j<=i;j++)
{
if(gcd(i,j)!=1)continue;
cerr<<i<<' '<<j<<' '<<check(i,j)<<endl;
}
*/
const int lim=1e9;//4000*4000;
struct frac
{
int p,q;
frac operator+(const frac &f)const{return {p+f.p,q+f.q};}
frac operator*(const int k)const{return {p*k,q*k};}
bool operator<(const frac &f)const{return 1ll*p*f.q<1ll*q*f.p;}
}ans{lim,1},l{1,1},r{1,0};
if(check(1,1))
{
ans={1,1};
}
int dir=0,fir=1;
while(1)
{
// cerr<<"gp "<<l.p<<"/"<<l.q<<'~'<<r.p<<"/"<<r.q<<' '<<dir<<endl;
if((l+r).p>lim or (l+r).q>lim)break;
if(dir==0)
{
int kl=(!fir),kr=min((lim-r.p)/max(l.p,1),(lim-r.q)/max(l.q,1));
// fir=0;
while(kl<kr)
{
int km=(kl+kr+1)/2;
frac tmp=l*km+r;
if(check(tmp.p,tmp.q))
{
if(tmp<ans)ans=tmp;
kl=km;
}
else
kr=km-1;
}
r=l*kl+r;
if(r<ans and check(r.p,r.q))ans=r;
dir^=1;
}
else
{
int kl=(!fir),kr=min((lim-l.p)/max(r.p,1),(lim-l.q)/max(r.q,1));
while(kl<kr)
{
int km=(kl+kr)/2;
frac tmp=l+r*km;
if(check(tmp.p,tmp.q))
{
if(tmp<ans)ans=tmp;
kr=km;
}
else
kl=km+1;
}
l=l+r*kl;
if(l<ans and check(l.p,l.q))ans=l;
dir^=1;
}
}
const int MOD=998244353;
auto poww=[&](long long x,int y)
{
long long ret=1;
while(y)
{
if(y&1)ret*=x,ret%=MOD;
x*=x,x%=MOD;
y>>=1;
}
return ret;
};
// cerr<<"ans = "<<ans.p<<'/'<<ans.q<<endl;
cout<<1ll*ans.p*poww(ans.q,MOD-2)%MOD<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
input:
3 3 3 1 3 2 3 1 2 12 6 2 3 5 7 1 9 4 8 1 2 7 11 4 5 3 4 2 3 1 2 4 4 1 1
output:
1 2 499122178
result:
ok 3 number(s): "1 2 499122178"
Test #2:
score: 0
Accepted
time: 13ms
memory: 3604kb
input:
2000 1000000000 1 259923446 367011266 1000000000 1 882434225 971573327 1000000000 1 41585677 470369580 1000000000 1 371902212 947250194 1000000000 1 787209148 924205796 1000000000 1 259074809 960876164 1000000000 1 148079314 188254573 1000000000 1 940091047 948318624 1000000000 1 40636497 743979446 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 2000 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 3564kb
input:
1000 1000000000 5 575330909 661595447 708422488 913945134 658050911 930246647 786571892 904549453 851755566 969150871 1000000000 2 198072104 844159589 8876188 644559580 1000000000 2 740802634 976972118 783909534 898449184 1000000000 2 871819537 941611957 465883854 640988372 1000000000 1 99458969 462...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 ...
result:
ok 1000 numbers
Test #4:
score: 0
Accepted
time: 18ms
memory: 3512kb
input:
500 1000000000 13 964546318 987364574 367845944 907446075 259314137 890312338 458318546 959971971 353677471 522446336 782931403 845199078 514387878 786979588 532634932 793056892 905393511 960628299 747423889 986373313 796099347 833069525 906969434 971335651 574582540 647534593 1000000000 6 987712893...
output:
3 1 3 1 1 1 1 1 1 3 2 1 1 1 3 1 2 1 1 2 1 3 1 1 1 2 1 2 2 1 1 1 1 1 1 1 3 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 1 3 1 2 1 1 1 1 2 3 1 1 1 1 1 1 1 3 2 1 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 1 1 2 1 1 2 1 1 1 2 1 4 1 2 1 4 1 3 1 1 1 1 1 2 1 1 4 1 ...
result:
ok 500 numbers
Test #5:
score: 0
Accepted
time: 38ms
memory: 3652kb
input:
250 1000000000 10 844342043 888135880 127033337 726074967 581308029 893912240 414276384 752837267 565680461 863374082 230362895 477723054 210479116 423381051 325072305 427826920 178306222 756423471 376470949 993759748 1000000000 2 468173597 607783582 266359996 863641680 1000000000 7 206599093 941381...
output:
2 1 2 1 3 3 1 1 1 2 1 2 2 1 3 5 2 1 1 1 2 1 2 1 3 1 2 1 3 499122178 1 1 1 1 3 1 1 1 3 3 3 1 4 1 1 1 1 1 1 1 1 5 1 4 2 1 3 1 1 1 2 5 2 1 2 6 2 2 1 2 1 1 1 5 8 2 1 2 1 1 2 2 2 1 1 5 8 3 1 1 1 8 2 6 1 1 4 2 1 1 1 1 2 2 1 2 1 1 1 1 1 1 2 1 2 1 1 4 1 1 3 1 2 3 3 2 5 1 1 1 3 2 1 1 1 3 1 1 2 1 1 1 1 3 1 1 ...
result:
ok 250 numbers
Test #6:
score: -100
Wrong Answer
time: 38ms
memory: 3808kb
input:
250 1000000000 4 10495745 465086423 465086424 609997778 396956207 663037010 253873206 396956206 1000000000 33 596279983 655818820 226461062 338625457 407323582 423049163 711408063 778512581 220274357 226461061 702491412 711408062 686978949 688730316 369564474 434159428 778512582 787885602 675683057 ...
output:
1 2 748683266 5 6 831870296 1 10 6 1 7 1 4 3 1 3 1 748683266 2 3 10 499122178 1 3 4 1 7 1 3 2 2 2 332748119 249561090 713031682 499122178 2 3 5 3 4 17 1 2 2 3 4 1 3 921456327 3 2 3 3 2 7 3 11 6 665496237 1 2 3 2 2 2 499122178 3 7 332748119 3 1 3 1 10 598946613 5 499122178 4 665496237 2 2 1 3 1 1 2 3...
result:
wrong answer 6th numbers differ - expected: '453747435', found: '831870296'