QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #711464 | #9519. Build a Computer | xyz123# | AC ✓ | 16ms | 30996kb | C++23 | 3.1kb | 2024-11-05 11:14:43 | 2024-11-05 11:14:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001],cn1,cn2,st1[1000001],st2[1000001],sm[1000001];
long long sm1[1000001],dp[1000001],si[1000001],nx[1000001],in[1000001],cnt,id[1000001];
char s[1000001],bg,ls;
struct p{long long q,w;bool operator < (const p &aa) const{return q>aa.q;};}l[1000001],m[1000001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
char t[4];
vector<p> qu[1000001];
void add(long long qq,long long ww,long long ee){qu[qq].push_back(p{ww,ee});in[ww]++;}
void ins(int qq,int ll,int rr,int nw,int L,int R)
{
int mid=((L+R)>>1);
if(qq==0) return;
if(qq==1)
{
for(int i=ll;i<=rr;i++) add(nw,2,i%2);
return;
}
// cout<<qq<<" "<<ll<<" "<<rr<<" "<<nw<<" "<<L<<" "<<R<<"\n";
if((rr-ll+1)==(1<<qq))
{
add(nw,h[qq-1],0);
add(nw,h[qq-1],1);
}
else
{
long long tt=(1<<qq);
if(rr<=mid)
{
++cnt;
add(nw,cnt,0);
ins(qq-1,ll,rr,cnt,L,mid);
}
else if(ll>mid)
{
++cnt;
add(nw,cnt,1);
ins(qq-1,ll,rr,cnt,mid+1,R);
}
else{
++cnt;
add(nw,cnt,0);
ins(qq-1,ll,mid,cnt,L,mid);
++cnt;
add(nw,cnt,1);
ins(qq-1,mid+1,rr,cnt,mid+1,R);
}
}
}
vector<int> qu1[1000001];
int main()
{
// freopen("1.in","r",stdin);
srand((unsigned)(time(0)^(*new int)));
fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
T=1;
scanf("%lld%lld",&a,&b);
for(int i=a;i<=b;i++)
{
for(int j=20;j>=0;j--)
{
if((1<<j)&i)
{
qu1[j].push_back(i-(1<<j));
break;
}
}
}
cnt=1;
for(int i=0;i<20;i++)
{
if(i==0) h[i]=++cnt;
else
{
h[i]=++cnt;
add(h[i],h[i-1],0);
add(h[i],h[i-1],1);
}
}
for(int i=0;i<=20;i++)
{
if(qu1[i].size()==0) continue;
if(i==0) add(1,2,1);
else add(1,++cnt,1);
long long L=qu1[i][0];
long long R=qu1[i][qu1[i].size()-1];
ins(i,L,R,cnt,0,(1<<i)-1);
}
for(int ii=1;ii<=cnt;ii++)
{
for(int i=2;i<=cnt;i++)
{
if(!v[i]&&in[i]==0)
{
v[i]=1;
for(int j=0;j<qu[i].size();j++) in[qu[i][j].q]--;
}
}
}
for(int i=1;i<=cnt;i++)
{
if(!v[i]) id[i]=++cn;
}
printf("%lld\n",cn);
for(int i=1;i<=cnt;i++)
{
if(!v[i])
{
int tt=qu[i].size();
printf("%d ",tt);
for(int j=0;j<qu[i].size();j++)
{
printf("%lld %lld ",id[qu[i][j].q],qu[i][j].w);
}printf("\n");
}
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 28600kb
input:
5 7
output:
5 1 3 1 0 2 4 0 5 1 1 2 1 2 2 0 2 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 7ms
memory: 28540kb
input:
10 27
output:
12 2 5 1 9 1 0 2 2 0 2 1 2 3 0 3 1 2 6 0 8 1 1 7 1 2 2 0 2 1 2 3 0 3 1 2 10 0 11 1 2 4 0 4 1 1 12 0 2 3 0 3 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 9ms
memory: 26484kb
input:
5 13
output:
10 2 4 1 7 1 0 2 2 0 2 1 2 5 0 6 1 1 2 1 2 2 0 2 1 2 8 0 9 1 2 3 0 3 1 1 10 0 2 2 0 2 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 15ms
memory: 30996kb
input:
1 1000000
output:
62 20 2 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 7ms
memory: 26552kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 14ms
memory: 28424kb
input:
7 9
output:
7 2 3 1 5 1 0 1 4 1 1 2 1 1 6 0 1 7 0 2 2 0 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 7ms
memory: 28560kb
input:
3 7
output:
5 2 4 1 5 1 0 2 2 0 2 1 1 2 1 2 3 0 3 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 4ms
memory: 28560kb
input:
1 5
output:
5 3 2 1 3 1 4 1 0 2 2 0 2 1 1 5 0 2 2 0 2 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 13ms
memory: 28600kb
input:
1 4
output:
5 3 2 1 3 1 4 1 0 2 2 0 2 1 1 5 0 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 14ms
memory: 28532kb
input:
8 9
output:
5 1 3 1 0 1 4 0 1 5 0 2 2 0 2 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 9ms
memory: 28548kb
input:
7 51
output:
14 4 6 1 8 1 9 1 10 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 1 7 1 1 2 1 2 4 0 4 1 2 5 0 5 1 2 11 0 12 1 2 5 0 5 1 1 13 0 1 14 0 2 3 0 3 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 14ms
memory: 26444kb
input:
51 79
output:
15 2 6 1 13 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 1 7 1 2 8 0 12 1 2 9 0 11 1 1 10 1 1 2 1 2 3 0 3 1 2 4 0 4 1 1 14 0 1 15 0 2 5 0 5 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 10ms
memory: 28476kb
input:
92 99
output:
12 1 4 1 0 2 2 0 2 1 2 5 0 9 1 1 6 1 1 7 1 1 8 1 2 3 0 3 1 1 10 0 1 11 0 1 12 0 2 3 0 3 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 14ms
memory: 26552kb
input:
27 36
output:
14 2 4 1 9 1 0 2 2 0 2 1 1 5 1 2 6 0 8 1 1 7 1 1 2 1 2 3 0 3 1 1 10 0 1 11 0 2 12 0 13 1 2 3 0 3 1 1 14 0 1 2 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 10ms
memory: 26368kb
input:
55 84
output:
19 2 6 1 12 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 1 7 1 2 8 0 11 1 1 9 1 1 10 1 1 2 1 2 4 0 4 1 1 13 0 2 14 0 15 1 2 5 0 5 1 1 16 0 2 17 0 18 1 2 3 0 3 1 1 19 0 1 2 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 6ms
memory: 28688kb
input:
297208 929600
output:
70 2 20 1 44 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 21 0 43 1 2 22 0 42 1 1 23 1 2 24 0 41 1 2 25 0 40 1 2 26 0 39 1 1 2...
result:
ok ok
Test #17:
score: 0
Accepted
time: 10ms
memory: 30540kb
input:
45728 589156
output:
67 5 20 1 36 1 37 1 38 1 39 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 21 0 35 1 1 22 1 1 23 1 2 24 0 34 1 2 25 0 33 1 1 26 1...
result:
ok ok
Test #18:
score: 0
Accepted
time: 9ms
memory: 28616kb
input:
129152 138000
output:
48 2 14 1 27 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 2 20 0 26 1 2 21 0 25 1 2 22 0 24 1 1 23 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 1 28 0 1 29 0 1 3...
result:
ok ok
Test #19:
score: 0
Accepted
time: 8ms
memory: 30360kb
input:
245280 654141
output:
68 3 20 1 37 1 38 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 1 21 1 1 22 1 2 23 0 36 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 7ms
memory: 28640kb
input:
202985 296000
output:
63 2 17 1 43 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 1 18 1 2 19 0 42 1 2 20 0 41 1 2 21 0 40 1 1 22 1 1 23 1 2 24 0 39 1 2 25 0 38 1 2 26 0 37 1 1 27 1 1 28 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 16ms
memory: 28328kb
input:
438671 951305
output:
69 2 20 1 46 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 1 21 1 2 22 0 45 1 1 23 1 2 24 0 44 1 1 25 1 1 26 1 2 27 0 43 1 2 28 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 14ms
memory: 27352kb
input:
425249 739633
output:
71 2 19 1 46 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 1 20 1 2 21 0 45 1 2 22 0 44 1 1 23 1 1 24 1 1 25 1 1 26 1 1 27 1 2 28 0 43 1 1 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 16ms
memory: 27816kb
input:
551207 961718
output:
75 1 19 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 20 0 48 1 2 21 0 47 1 2 22 0 46 1 2 23 0 45 1 1 24 1 1 25 1 2 26 0 44 1 1 27 1 2 28 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 10ms
memory: 30416kb
input:
114691 598186
output:
74 4 20 1 48 1 49 1 50 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 1 21 1 1 22 1 2 23 0 47 1 2 24 0 46 1 2 25 0 45 1 2 26 0 44 1...
result:
ok ok
Test #25:
score: 0
Accepted
time: 10ms
memory: 28680kb
input:
234654 253129
output:
57 1 15 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 1 16 1 1 17 1 2 18 0 38 1 2 19 0 37 1 1 20 1 2 21 0 36 1 1 22 1 2 23 0 35 1 2 24 0 34 1 1 25 1 2 26 0 33 1 2 27 0 32 1 1 28 1 1 29 1 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 26628kb
input:
554090 608599
output:
61 1 17 1 0 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 1 18 0 1 19 0 2 20 0 43 1 2 21 0 42 1 1 22 1 1 23 1 1 24 1 2 25 0 41 1 1 26 1 2 27 0 40 1 2 28 0 39 1 2 29 0 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed