QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #341318 | #1428. Grp | rageOfThunder# | TL | 1213ms | 142916kb | C++14 | 5.7kb | 2024-02-29 17:42:32 | 2024-02-29 17:42:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
const long long mod=1e9+7;
long long T,S,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,st[1000001],sm[1000001],de[1000001],inf=1e9,vi[1000001],vii[1000001],vv[1000001];
char s[1000001];
struct p{int q,w,e;}l[5000001];
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;}
void add(long long qq,long long ww)
{
l[++o].q=ww,l[o].w=h[qq],l[o].e=1,h[qq]=o;
swap(qq,ww);
l[++o].q=ww,l[o].w=h[qq],l[o].e=0,h[qq]=o;
}
vector<int> qu[200001],qu1[200001];
map<int,int> id[101];
queue<long long> quu;
bool bfs()
{
memset(de,0,sizeof(de));quu.push(S);de[S]=1;
while(!quu.empty())
{
long long r=quu.front();quu.pop();
for(int i=h[r];i;i=l[i].w) if(l[i].e&&!de[l[i].q]) de[l[i].q]=de[r]+1,quu.push(l[i].q);
}
return de[T];
}
long long dfs(long long qq,long long ww)
{
if(qq==T) return ww;long long gg=0;
for(int i=h[qq];i;i=l[i].w)
{
if(de[l[i].q]==de[qq]+1&&ww&&l[i].e)
{
long long ee=dfs(l[i].q,min(ww,(long long)l[i].e));
l[i].e-=ee,l[i^1].e+=ee,ww-=ee,gg+=ee;
}
}if(!gg) de[qq]=0;
return gg;
}
vector<int> ve[1000001],tmp;
int main()
{
// freopen("1.in","r",stdin);
scanf("%lld%lld",&a,&b);
for(int k=1;k<(1<<a);k++)
{
cn=0;
for(int i=0;i<a;i++)
{
if((1<<i)&k) ++cn;
}
qu[cn].push_back(k);
id[cn][k]=qu[cn].size();
sm[k]=cn;
}
for(int i=0;i<qu[b].size();i++)
{
++an;ve[an].push_back(qu[b][i]);
}
// cout<<an;return 0;
for(int i=1;i<=(b-1)/2;i++)
{
int tt=b-i;
S=qu[tt].size()+qu[i].size()+1,T=S+1;h[S]=h[T]=0;
o=1;for(int j=0;j<qu[tt].size()+qu[i].size();j++) h[j+1]=0;
for(int j=0;j<qu[tt].size();j++) add(S,j+1);
for(int j=0;j<qu[i].size();j++) add(qu[tt].size()+j+1,T);
for(int j=0;j<qu[tt].size();j++)
{
cn=0;
for(int k=0;k<a;k++)
{
if(!((1<<k)&qu[tt][j])) st[++cn]=k;
}
for(int k=0;k<(1<<cn);k++)
{
if(sm[k]==i)
{
long long hh=0;
for(int ii=0;ii<cn;ii++)
{
if(((1<<ii)&k)) hh|=(1<<st[ii+1]);
}
// cout<<id[i][hh]<<" "<<qu[i][id[i][hh]-1]<<"\n";
add(j+1,qu[tt].size()+id[i][hh]);
}
}
}
long long hh=0;
while(bfs()) hh+=dfs(S,inf);
// an+=qu[tt].size()+qu[i].size()-hh;
for(int j=0;j<qu[tt].size();j++)
{
int gg=j+1,fl=0;
for(int k=h[gg];k;k=l[k].w)
{
if(l[k].q==S&&l[k].e==1)
{
fl=1;break;
}
}
if(!fl)
{
++an;
ve[an].push_back(qu[tt][j]);continue;
}
++an;ve[an].push_back(qu[tt][j]);
for(int k=h[gg];k;k=l[k].w)
{
if(l[k].q>qu[tt].size()&&l[k].q!=S&&l[k].e==0)
{
ve[an].push_back(qu[i][l[k].q-qu[tt].size()-1]);
break;
}
}
}
}
if(b%2==0)
{
int tt=b/2,yy=0,ff=qu[tt].size()/2;
for(int i=0;i<qu[tt].size();i++)
{
cn=0;
for(int j=0;j<a;j++) v[j]=0;
for(int j=0;j<a;j++)
{
if(((1<<j)&qu[tt][i]))
{
st[++cn]=j;
v[j]=1;
}
}
long long hh=0;
for(int j=1;j<=cn;j++)
{
int gg=st[j];
while(1)
{
if(!v[gg])
{
hh|=(1<<gg);v[gg]=1;
break;
}++gg;
if(gg==a) gg=0;
}
}
vi[i+1]=id[tt][hh];
}
memset(v,0,sizeof(v));
for(int i=1;i<=qu[tt].size();i++) vii[i]=vi[i];
memset(vi,0,sizeof(vi));
for(int i=1;i<=qu[tt].size();i++)
{
// cout<<i<<" "<<vv[i]<<"\n";
// return 0;
if(vv[i]) continue;
long long tt=i,gg=0;
cn=0;
while(!vv[tt])
{
++gg;st[++cn]=tt;vv[tt]=1;
tt=vii[tt];
}
for(int j=1;j<=cn/2;j++)
{
v[st[j*2-1]]=v[st[j*2]]=1;
vi[st[j*2-1]]=st[j*2];
vi[st[j*2]]=st[j*2-1];++yy;
}
}
cn=0;
for(int i=0;i<qu[tt].size();i++)
{
cn=0;
for(int k=0;k<a;k++)
{
if(!((1<<k)&qu[tt][i])) st[++cn]=k;
}
for(int k=0;k<(1<<cn);k++)
{
if(sm[k]==tt)
{
long long hh=0;
for(int ii=0;ii<cn;ii++)
{
if(((1<<ii)&k)) hh|=(1<<st[ii+1]);
}
qu1[i+1].push_back(id[tt][hh]);
}
}
if(!v[i+1]) tmp.push_back(i+1);
}
// cout<<yy<<" "<<ff<<"\n";
// for(int i=0;i<tmp.size();i++) cout<<tmp[i]<<" ";cout<<"\n";
while(yy<ff)
{
long long ttt=rnd()%tmp.size(),fl=0;
ttt=tmp[ttt];
// cout<<ttt<<" "<<yy<<" "<<ff<<" "<<qu1[ttt].size()<<"\n";
if(qu1[ttt].size()==0) return 0;
random_shuffle(qu1[ttt].begin(),qu1[ttt].end());
for(int i=0;i<qu1[ttt].size();i++)
{
if(!v[qu1[ttt][i]])
{
vi[qu1[ttt][i]]=ttt,vi[ttt]=qu1[ttt][i];
v[qu1[ttt][i]]=v[ttt]=1;++yy;
fl=1;
break;
}
}
if(!fl)
{
int vv=rnd()%qu1[ttt].size(),uu=qu1[ttt][vv];
v[vi[uu]]=0;vi[vi[uu]]=0;
vi[ttt]=uu,vi[uu]=ttt;v[ttt]=1;
}
tmp.clear();
for(int i=1;i<=qu[tt].size();i++) if(!v[i]) tmp.push_back(i);
}
// for(int i=1;i<=qu[tt].size();i++)
// {
// cout<<i<<" "<<vi[i]<<"\n";
// }
// cout<<yy<<" "<<ff<<"\n";
memset(v,0,sizeof(v));
for(int i=1;i<=qu[tt].size();i++)
{
if(v[i]) continue;
++an;
v[i]=1;ve[an].push_back(qu[tt][i-1]);
if(vi[i]) v[vi[i]]=1,ve[an].push_back(qu[tt][vi[i]-1]);
}
}
printf("%lld\n",an);
for(int i=1;i<=an;i++)
{
int tt=ve[i].size();
printf("%d ",tt);
for(int j=0;j<ve[i].size();j++)
{
tt=ve[i][j];
for(int k=0;k<a;k++)
{
if(((1<<k)&tt))
{
putchar(k+'a');
}
}
if(j+1!=ve[i].size()) printf(" ");
}
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 66192kb
input:
3 2
output:
5 1 ab 1 ac 1 bc 2 a b 1 c
result:
ok ok, n = 3, k = 2, groups = 5
Test #2:
score: 0
Accepted
time: 4ms
memory: 53812kb
input:
3 3
output:
4 1 abc 2 ab c 2 ac b 2 bc a
result:
ok ok, n = 3, k = 3, groups = 4
Test #3:
score: 0
Accepted
time: 7ms
memory: 42008kb
input:
1 1
output:
1 1 a
result:
ok ok, n = 1, k = 1, groups = 1
Test #4:
score: 0
Accepted
time: 3ms
memory: 41072kb
input:
2 1
output:
2 1 a 1 b
result:
ok ok, n = 2, k = 1, groups = 2
Test #5:
score: 0
Accepted
time: 3ms
memory: 64980kb
input:
2 2
output:
2 1 ab 2 a b
result:
ok ok, n = 2, k = 2, groups = 2
Test #6:
score: 0
Accepted
time: 0ms
memory: 41988kb
input:
3 1
output:
3 1 a 1 b 1 c
result:
ok ok, n = 3, k = 1, groups = 3
Test #7:
score: 0
Accepted
time: 0ms
memory: 56676kb
input:
4 3
output:
10 1 abc 1 abd 1 acd 1 bcd 1 ab 1 ac 2 bc d 2 ad c 2 bd a 2 cd b
result:
ok ok, n = 4, k = 3, groups = 10
Test #8:
score: 0
Accepted
time: 0ms
memory: 72540kb
input:
4 4
output:
8 1 abcd 2 abc d 2 abd c 2 acd b 2 bcd a 2 ab cd 2 ac bd 2 bc ad
result:
ok ok, n = 4, k = 4, groups = 8
Test #9:
score: 0
Accepted
time: 4ms
memory: 56444kb
input:
5 3
output:
20 1 abc 1 abd 1 acd 1 bcd 1 abe 1 ace 1 bce 1 ade 1 bde 1 cde 1 ab 1 ac 1 bc 1 ad 1 bd 2 cd e 2 ae b 2 be a 2 ce d 2 de c
result:
ok ok, n = 5, k = 3, groups = 20
Test #10:
score: 0
Accepted
time: 4ms
memory: 74492kb
input:
5 4
output:
20 1 abcd 1 abce 1 abde 1 acde 1 bcde 1 abc 1 abd 1 acd 2 bcd e 1 abe 1 ace 2 bce d 2 ade c 2 bde a 2 cde b 2 ab de 2 ac bd 2 bc ae 2 ad ce 2 cd be
result:
ok ok, n = 5, k = 4, groups = 20
Test #11:
score: 0
Accepted
time: 6ms
memory: 73096kb
input:
6 4
output:
43 1 abcd 1 abce 1 abde 1 acde 1 bcde 1 abcf 1 abdf 1 acdf 1 bcdf 1 abef 1 acef 1 bcef 1 adef 1 bdef 1 cdef 1 abc 1 abd 1 acd 1 bcd 1 abe 1 ace 1 bce 1 ade 1 bde 2 cde f 1 abf 1 acf 1 bcf 1 adf 1 bdf 2 cdf e 2 aef b 2 bef a 2 cef d 2 def c 2 ab cd 2 ac bd 2 bc de 2 ad cf 2 ae bf 2 be df 2 ce af 1 ef
result:
ok ok, n = 6, k = 4, groups = 43
Test #12:
score: 0
Accepted
time: 4ms
memory: 55548kb
input:
10 7
output:
792 1 abcdefg 1 abcdefh 1 abcdegh 1 abcdfgh 1 abcefgh 1 abdefgh 1 acdefgh 1 bcdefgh 1 abcdefi 1 abcdegi 1 abcdfgi 1 abcefgi 1 abdefgi 1 acdefgi 1 bcdefgi 1 abcdehi 1 abcdfhi 1 abcefhi 1 abdefhi 1 acdefhi 1 bcdefhi 1 abcdghi 1 abceghi 1 abdeghi 1 acdeghi 1 bcdeghi 1 abcfghi 1 abdfghi 1 acdfghi 1 bcdf...
result:
ok ok, n = 10, k = 7, groups = 792
Test #13:
score: 0
Accepted
time: 29ms
memory: 73756kb
input:
13 10
output:
6364 1 abcdefghij 1 abcdefghik 1 abcdefghjk 1 abcdefgijk 1 abcdefhijk 1 abcdeghijk 1 abcdfghijk 1 abcefghijk 1 abdefghijk 1 acdefghijk 1 bcdefghijk 1 abcdefghil 1 abcdefghjl 1 abcdefgijl 1 abcdefhijl 1 abcdeghijl 1 abcdfghijl 1 abcefghijl 1 abdefghijl 1 acdefghijl 1 bcdefghijl 1 abcdefghkl 1 abcdefg...
result:
ok ok, n = 13, k = 10, groups = 6364
Test #14:
score: 0
Accepted
time: 3ms
memory: 55852kb
input:
9 9
output:
256 1 abcdefghi 2 abcdefgh i 2 abcdefgi h 2 abcdefhi g 2 abcdeghi f 2 abcdfghi e 2 abcefghi d 2 abdefghi c 2 acdefghi b 2 bcdefghi a 2 abcdefg hi 2 abcdefh gi 2 abcdegh fi 2 abcdfgh ei 2 abcefgh di 2 abdefgh ci 2 acdefgh bi 2 bcdefgh ai 2 abcdefi gh 2 abcdegi fh 2 abcdfgi eh 2 abcefgi dh 2 abdefgi c...
result:
ok ok, n = 9, k = 9, groups = 256
Test #15:
score: 0
Accepted
time: 8ms
memory: 74768kb
input:
11 8
output:
1584 1 abcdefgh 1 abcdefgi 1 abcdefhi 1 abcdeghi 1 abcdfghi 1 abcefghi 1 abdefghi 1 acdefghi 1 bcdefghi 1 abcdefgj 1 abcdefhj 1 abcdeghj 1 abcdfghj 1 abcefghj 1 abdefghj 1 acdefghj 1 bcdefghj 1 abcdefij 1 abcdegij 1 abcdfgij 1 abcefgij 1 abdefgij 1 acdefgij 1 bcdefgij 1 abcdehij 1 abcdfhij 1 abcefhi...
result:
ok ok, n = 11, k = 8, groups = 1584
Test #16:
score: 0
Accepted
time: 149ms
memory: 70928kb
input:
15 9
output:
25883 1 abcdefghi 1 abcdefghj 1 abcdefgij 1 abcdefhij 1 abcdeghij 1 abcdfghij 1 abcefghij 1 abdefghij 1 acdefghij 1 bcdefghij 1 abcdefghk 1 abcdefgik 1 abcdefhik 1 abcdeghik 1 abcdfghik 1 abcefghik 1 abdefghik 1 acdefghik 1 bcdefghik 1 abcdefgjk 1 abcdefhjk 1 abcdeghjk 1 abcdfghjk 1 abcefghjk 1 abde...
result:
ok ok, n = 15, k = 9, groups = 25883
Test #17:
score: 0
Accepted
time: 16ms
memory: 71492kb
input:
13 12
output:
4953 1 abcdefghijkl 1 abcdefghijkm 1 abcdefghijlm 1 abcdefghiklm 1 abcdefghjklm 1 abcdefgijklm 1 abcdefhijklm 1 abcdeghijklm 1 abcdfghijklm 1 abcefghijklm 1 abdefghijklm 1 acdefghijklm 1 bcdefghijklm 1 abcdefghijk 1 abcdefghijl 1 abcdefghikl 1 abcdefghjkl 1 abcdefgijkl 1 abcdefhijkl 1 abcdeghijkl 1 ...
result:
ok ok, n = 13, k = 12, groups = 4953
Test #18:
score: 0
Accepted
time: 3ms
memory: 65492kb
input:
6 2
output:
18 1 ab 1 ac 1 bc 1 ad 1 bd 1 cd 1 ae 1 be 1 ce 1 de 1 af 1 bf 1 cf 1 df 1 ef 2 a b 2 c d 2 e f
result:
ok ok, n = 6, k = 2, groups = 18
Test #19:
score: 0
Accepted
time: 0ms
memory: 72292kb
input:
7 4
output:
81 1 abcd 1 abce 1 abde 1 acde 1 bcde 1 abcf 1 abdf 1 acdf 1 bcdf 1 abef 1 acef 1 bcef 1 adef 1 bdef 1 cdef 1 abcg 1 abdg 1 acdg 1 bcdg 1 abeg 1 aceg 1 bceg 1 adeg 1 bdeg 1 cdeg 1 abfg 1 acfg 1 bcfg 1 adfg 1 bdfg 1 cdfg 1 aefg 1 befg 1 cefg 1 defg 1 abc 1 abd 1 acd 1 bcd 1 abe 1 ace 1 bce 1 ade 1 bd...
result:
ok ok, n = 7, k = 4, groups = 81
Test #20:
score: 0
Accepted
time: 3ms
memory: 42868kb
input:
12 1
output:
12 1 a 1 b 1 c 1 d 1 e 1 f 1 g 1 h 1 i 1 j 1 k 1 l
result:
ok ok, n = 12, k = 1, groups = 12
Test #21:
score: 0
Accepted
time: 7ms
memory: 65588kb
input:
7 2
output:
25 1 ab 1 ac 1 bc 1 ad 1 bd 1 cd 1 ae 1 be 1 ce 1 de 1 af 1 bf 1 cf 1 df 1 ef 1 ag 1 bg 1 cg 1 dg 1 eg 1 fg 2 a b 2 c d 2 e f 1 g
result:
ok ok, n = 7, k = 2, groups = 25
Test #22:
score: 0
Accepted
time: 21ms
memory: 58124kb
input:
13 9
output:
6721 1 abcdefghi 1 abcdefghj 1 abcdefgij 1 abcdefhij 1 abcdeghij 1 abcdfghij 1 abcefghij 1 abdefghij 1 acdefghij 1 bcdefghij 1 abcdefghk 1 abcdefgik 1 abcdefhik 1 abcdeghik 1 abcdfghik 1 abcefghik 1 abdefghik 1 acdefghik 1 bcdefghik 1 abcdefgjk 1 abcdefhjk 1 abcdeghjk 1 abcdfghjk 1 abcefghjk 1 abdef...
result:
ok ok, n = 13, k = 9, groups = 6721
Test #23:
score: 0
Accepted
time: 6ms
memory: 67480kb
input:
12 2
output:
72 1 ab 1 ac 1 bc 1 ad 1 bd 1 cd 1 ae 1 be 1 ce 1 de 1 af 1 bf 1 cf 1 df 1 ef 1 ag 1 bg 1 cg 1 dg 1 eg 1 fg 1 ah 1 bh 1 ch 1 dh 1 eh 1 fh 1 gh 1 ai 1 bi 1 ci 1 di 1 ei 1 fi 1 gi 1 hi 1 aj 1 bj 1 cj 1 dj 1 ej 1 fj 1 gj 1 hj 1 ij 1 ak 1 bk 1 ck 1 dk 1 ek 1 fk 1 gk 1 hk 1 ik 1 jk 1 al 1 bl 1 cl 1 dl 1 ...
result:
ok ok, n = 12, k = 2, groups = 72
Test #24:
score: 0
Accepted
time: 1213ms
memory: 142916kb
input:
17 14
output:
99416 1 abcdefghijklmn 1 abcdefghijklmo 1 abcdefghijklno 1 abcdefghijkmno 1 abcdefghijlmno 1 abcdefghiklmno 1 abcdefghjklmno 1 abcdefgijklmno 1 abcdefhijklmno 1 abcdeghijklmno 1 abcdfghijklmno 1 abcefghijklmno 1 abdefghijklmno 1 acdefghijklmno 1 bcdefghijklmno 1 abcdefghijklmp 1 abcdefghijklnp 1 abc...
result:
ok ok, n = 17, k = 14, groups = 99416
Test #25:
score: 0
Accepted
time: 56ms
memory: 67128kb
input:
17 5
output:
9248 1 abcde 1 abcdf 1 abcef 1 abdef 1 acdef 1 bcdef 1 abcdg 1 abceg 1 abdeg 1 acdeg 1 bcdeg 1 abcfg 1 abdfg 1 acdfg 1 bcdfg 1 abefg 1 acefg 1 bcefg 1 adefg 1 bdefg 1 cdefg 1 abcdh 1 abceh 1 abdeh 1 acdeh 1 bcdeh 1 abcfh 1 abdfh 1 acdfh 1 bcdfh 1 abefh 1 acefh 1 bcefh 1 adefh 1 bdefh 1 cdefh 1 abcgh...
result:
ok ok, n = 17, k = 5, groups = 9248
Test #26:
score: -100
Time Limit Exceeded
input:
17 12