QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698499 | #9519. Build a Computer | AnotherDayofSun# | AC ✓ | 4ms | 15688kb | C++14 | 3.6kb | 2024-11-01 19:59:25 | 2024-11-01 19:59:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define SZ(x) ((int)x.size())
#define pii pair<int,int>
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define foR(i,k,j) for(int i=(k);i>=(j);i--)
#define For(i,k,j) for(int i=(k);i<=(j);i++)
#define Foe(i,u) for(int i=lst[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define Fin(s) freopen(s,"r",stdin)
#define Fout(s) freopen(s,"w",stdout)
#define file(s) Fin(s".in"),Fout(s".out")
#define INF ((1<<30)-1)
//#define int long long
const int P=998244353; //
using namespace std;
template<typename T>inline void ckmax(T &a,T b) {(a<b)&&(a=b);}
template<typename T>inline void ckmin(T &a,T b) {(a>b)&&(a=b);}
inline int mul(int a,int b) {return 1ll*a*b%P;}
inline int add(int a,int b) {return a+b>=P?a+b-P:a+b;}
inline int sub(int a,int b) {return a-b>=0?a-b:a-b+P;}
inline void mulmod(int &a,int b) {a=mul(a, b);}
inline void addmod(int &a,int b) {((a+=b)>=P)&&(a-=P);}
inline void submod(int &a,int b) {((a-=b)<0)&&(a+=P);}
inline int ksm(int a,int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline void fprint(const vector<int> &f) {for(int i=0;i<(int)f.size();i++) fprintf(stderr,"%d ",f[i]); fprintf(stderr,"\n");}
inline int inv(int a) {return ksm(a,P-2);}
namespace FastIO {
const int SIZE=1<<16; char buf[SIZE],obuf[SIZE],str[64]; int bi=SIZE,bn=SIZE,opt;
int read(char *s) {
while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
}
bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
void write(int x) {
if(!x) obuf[opt++]='0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
if (opt>=(SIZE>>1)){fwrite(obuf,1,opt,stdout); opt=0;}
}
void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf,1,opt,stdout); opt=0;}}
void Fflush() {if (opt) fwrite(obuf,1,opt,stdout); opt=0;}
};
inline int read() {int x; FI(x); return x;}
const int MN=5e5+5;
vi g[MN]; int tot,rt,mx;
void getans(int l,int r,int L,int R,int dep) {
// cerr<<k<<' '<<l<<' '<<r<<endl;
if(L<=l&&r<=R) {
mx=max(mx,dep);
return;
}
int mid=(l+r)>>1;
if(L<=mid) getans(l,mid,L,R,dep-1);
if(mid<R) getans(mid+1,r,L,R,dep-1);
}
void build(int &k,int l,int r,int L,int R,int dep,int lz,int fr) {
if(lz||fr==-1) {
if(l!=r) k=++tot;
else k=1;
}
if(lz||fr==-1) fr=k;
if(L<=l&&r<=R) {
if(dep>=1) {
g[fr].pb(dep);
g[fr].pb(-dep);
}
return;
}
int mid=(l+r)>>1;
int lc=0,rc=0;
if(L<=mid) {
build(lc,l,mid,L,R,dep-1,lz,fr);
if(lc) g[fr].pb(-lc);
}
if(mid<R) build(rc,mid+1,r,L,R,dep-1,1,fr),g[fr].pb(rc);
}
void works() {
int L=read(),R=read(); getans(0,(1<<20)-1,L,R,20);
tot++; For(i,0,mx-2) tot++,g[tot].pb(tot-1),g[tot].pb(1-tot);
build(rt,0,(1<<20)-1,L,R,20,0,-1);
printf("%d\n",tot);
For(i,1,tot) {
printf("%d ",SZ(g[i]));
for(auto it:g[i]) {
printf("%d %d ",abs(it),it>0);
}
printf("\n");
}
}
int main(){
#ifdef wasa855
freopen("pro.in","r",stdin);
freopen("pro.out","w",stdout);
#endif
int T=1;
while(T--) {
works();
}
return FastIO::Fflush(),0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 15580kb
input:
5 7
output:
5 0 1 3 1 2 4 0 5 1 1 1 1 2 1 1 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 15512kb
input:
10 27
output:
12 0 2 1 1 1 0 2 2 1 2 0 2 5 1 9 1 2 6 0 8 1 1 7 1 2 1 1 1 0 2 2 1 2 0 2 10 0 11 1 2 3 1 3 0 1 12 0 2 2 1 2 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 15572kb
input:
5 13
output:
10 0 2 1 1 1 0 2 4 1 7 1 2 5 0 6 1 1 1 1 2 1 1 1 0 2 8 0 9 1 2 2 1 2 0 1 10 0 2 1 1 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 15564kb
input:
1 1000000
output:
62 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 20 1 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...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 15572kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 15556kb
input:
7 9
output:
7 0 2 3 1 5 1 1 4 1 1 1 1 1 6 0 1 7 0 2 1 1 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 3ms
memory: 15576kb
input:
3 7
output:
5 0 2 1 1 1 0 2 4 1 5 1 1 1 1 2 2 1 2 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 3ms
memory: 15572kb
input:
1 5
output:
5 0 3 1 1 3 1 4 1 2 1 1 1 0 1 5 0 2 1 1 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 15516kb
input:
1 4
output:
5 0 3 1 1 3 1 4 1 2 1 1 1 0 1 5 0 1 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 15508kb
input:
8 9
output:
5 0 1 3 1 1 4 0 1 5 0 2 1 1 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 3ms
memory: 15504kb
input:
7 51
output:
14 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 4 6 1 8 1 9 1 10 1 1 7 1 1 1 1 2 3 1 3 0 2 4 1 4 0 2 11 0 12 1 2 4 1 4 0 1 13 0 1 14 0 2 2 1 2 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 3ms
memory: 15604kb
input:
51 79
output:
15 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 6 1 13 1 1 7 1 2 8 0 12 1 2 9 0 11 1 1 10 1 1 1 1 2 2 1 2 0 2 3 1 3 0 1 14 0 1 15 0 2 4 1 4 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 15568kb
input:
92 99
output:
12 0 2 1 1 1 0 1 4 1 2 5 0 9 1 1 6 1 1 7 1 1 8 1 2 2 1 2 0 1 10 0 1 11 0 1 12 0 2 2 1 2 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 15548kb
input:
27 36
output:
14 0 2 1 1 1 0 2 4 1 9 1 1 5 1 2 6 0 8 1 1 7 1 1 1 1 2 2 1 2 0 1 10 0 1 11 0 2 12 0 13 1 2 2 1 2 0 1 14 0 1 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 15688kb
input:
55 84
output:
19 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 6 1 12 1 1 7 1 2 8 0 11 1 1 9 1 1 10 1 1 1 1 2 3 1 3 0 1 13 0 2 14 0 15 1 2 4 1 4 0 1 16 0 2 17 0 18 1 2 2 1 2 0 1 19 0 1 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 15500kb
input:
297208 929600
output:
70 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 20 1 44 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 27 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 15584kb
input:
45728 589156
output:
67 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 5 20 1 36 1 37 1 38 1 39 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: 0ms
memory: 15620kb
input:
129152 138000
output:
48 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 14 1 27 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 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 1 28 0 1 29 0 1 30 0 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 15624kb
input:
245280 654141
output:
68 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 3 20 1 37 1 38 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 29...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 15568kb
input:
202985 296000
output:
63 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 17 1 43 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 1 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 4ms
memory: 15568kb
input:
438671 951305
output:
69 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 20 1 46 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 0 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 15568kb
input:
425249 739633
output:
71 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 19 1 46 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 29...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 15588kb
input:
551207 961718
output:
75 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 1 19 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 0 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 15520kb
input:
114691 598186
output:
74 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 4 20 1 48 1 49 1 50 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: 0ms
memory: 15588kb
input:
234654 253129
output:
57 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 1 15 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 1...
result:
ok ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 15636kb
input:
554090 608599
output:
61 0 2 1 1 1 0 2 2 1 2 0 2 3 1 3 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 1 17 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 38...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed