QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #153401 | #6818. Barrel Theory | linnins | AC ✓ | 9ms | 1752kb | C++14 | 5.5kb | 2023-08-30 00:15:19 | 2023-08-30 00:15:20 |
Judging History
answer
#include<cstdio>
using namespace std;
int Ans[100500];
int lowbit(int n)
{
return (n)&(-1*n);
}
int main()
{
// freopen("k2.out","w",stdout);
// freopen("data.txt","r",stdin);
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
long long n,m;
scanf("%lld%lld",&n,&m);
if(n == m and n!=1 and n%2 != 1)
{
printf("YES\n");
for(int i=1;i<=n;i++)
printf("1 ");
printf("\n");
continue;
}
// if(T == 4194)
// {
// if(i != 1893)
// continue;
// else
// printf("%d %d",n,m);
// }
for(int i=1;i<=n;i++)
{
Ans[i] = 0;
}
if(m<n or n == 1)
{
printf("NO\n");
continue;
}
if(n == 2)
{
if(((m/2)^(m/2+m%2)) >= m/2)
{
printf("NO\n");
continue;
}
printf("YES\n");
printf("%d %d\n",m/2,m/2+m%2);
continue;
}
if(n == 3)
{
if(m%2 == 0)
{
if(lowbit(m) == m)
{
if(m<=8)
{
printf("NO\n");
continue;
}
else
{
printf("YES\n");
printf("%d %d %d\n",3*m/16,7*m/16,6*m/16);
continue;
}
}
else
{
printf("YES\n");
printf("%d %d %d\n",lowbit(m)/2,m/2,m/2-lowbit(m)/2);
continue;
}
}
else
{
if(lowbit(m-1) == m-1)
{
if(m<=17)
{
printf("NO\n");
continue;
}
else
{
printf("YES\n");
printf("%d %d %d\n",3*m/16,6*m/16+1,7*m/16);
continue;
}
}
else if(lowbit(m-3) == m-3)
{
if(m<=19)
{
printf("NO\n");
continue;
}
else
{
printf("YES\n");
printf("%d %d %d\n",7,(m-7)/2-1,(m-7)/2+1);
continue;
}
}
else
{
if(m == 13)
{
printf("YES\n");
printf("3 4 6\n");
continue;
}
else if(m == 15)
{
printf("YES\n");
printf("3 5 7\n");
continue;
}
else if(m <= 19)
{
printf("NO\n");
continue;
}
else
{
if(m%8 == 5)
{
printf("YES\n");
printf("%d %d %d\n",(m-5)/2,(m-5)/2+2,3);
}
else if(m%8 == 7)
{
printf("YES\n");
printf("%d %d %d\n",(m-5)/2,(m-5)/2+2,3);
}
else if(m%16 == 1)
{
int t = 17,a = 3,b = 7, c = 7;
printf("YES\n");
printf("%d %d %d\n",(m-t)/2+a,(m-t)/2+b,c);
}
else if(m%16 == 3)
{
int t = 19,a = 5,b = 7, c = 7;
printf("YES\n");
printf("%d %d %d\n",(m-t)/2+a,(m-t)/2+b,c);
}
else if(m%16 == 9)
{
int t = 9,a = 0,b = 4, c = 5;
printf("YES\n");
printf("%d %d %d\n",(m-t)/2+a,(m-t)/2+b,c);
}
else if(m%16 == 11)
{
int t = 11,a = 1,b = 5, c = 5;
printf("YES\n");
printf("%d %d %d\n",(m-t)/2+a,(m-t)/2+b,c);
}
continue;
}
}
}
}
else if(n%2 == 0)
{
if(m%2 == 0)
{
for(int i=1;i<=n-2;i++)
Ans[i] = 1;
Ans[n-1] = (m-(n-2))/2;
Ans[n] = (m-(n-2))/2;
}
else
{
if(2*n+1>m)
{
printf("NO\n");
continue;
}
else
/*
4 11
2 2 x x 7
*/
{
for(int i=1;i<=n-2;i++)
Ans[i] = 2;
Ans[1] += 1;
m -= (n-2)*2+1;
if(m<=3)
{
printf("NO\n");
continue;
}
else
{
Ans[n-1] = m/2;
Ans[n] = m/2 + m%2;
}
}
}
}
else//n是奇数
{
if(m%2==0)//m是偶数
{
for(int i=1;i<=n-3;i++)
Ans[i] = 1;
m -= (n-3);
if(m<=5)
{
printf("NO\n");
continue;
}
else
{
if(m == lowbit(m))
{
if(m <=4)
{
printf("NO\n");
continue;
}
else
{
Ans[1] = 2;
Ans[2] = 2;
m-=2;
Ans[n-2] = lowbit(m)/2;
Ans[n-1] = (m-lowbit(m))/2+lowbit(m)/2;
Ans[n] = (m-lowbit(m))/2;
}
}
else
{
Ans[n-2] = lowbit(m)/2;
Ans[n-1] = (m-lowbit(m))/2+lowbit(m)/2;
Ans[n] = (m-lowbit(m))/2;
}
}
}
else//m是奇数
{
if(n*2+1>m)
{
printf("NO\n");
continue;
}
else
{
for(int i=1;i<=n-3;i++)
{
Ans[i] = 2;
}
Ans[1] = 3;
m -= (n-3)*2+1;
if(lowbit(m) == 2 and lowbit(m-2) == m-2)
{
if(m<=10)
{
printf("NO\n");
continue;
}
Ans[1] += 2;
Ans[2] += 3;
m -= 5;
// 5 4 2 2 2 x x x 6 2 4 12 1 1 0 0
}
if(m == lowbit(m))
{
if(m <= 8)
{
printf("NO\n");
continue;
}
else
{
Ans[1] = 5;
Ans[2] = 4;
m = m-4;
Ans[n-2] = lowbit(m)/2;
Ans[n-1] = m/2-lowbit(m)/2;
Ans[n] = m/2;
}
}
else if(lowbit(m) == 2)
{
if(m<=10)
{
printf("NO\n");
continue;
}
else
{
Ans[1] = 3;
Ans[2] = 3;
m -= 2;
Ans[n-2] = lowbit(m)/2;
Ans[n-1] = m/2 - lowbit(m)/2+1;
Ans[n] = m/2;
}
}
else
{
int mid = m%2;
m -= mid;
Ans[n-1] = m/2-lowbit(m)/2+mid;
Ans[n-2] = lowbit(m)/2;
Ans[n] = m/2;
}
}
}
}
printf("YES\n");
for(int i=1;i<=n;i++)
{
printf("%d ",Ans[i]);
}
printf("\n");
}
return 0;
}
/*
3 3 2 5 6
0 0 1 1
0 0 1 1
0 0 1 0
0 1 0 1
0 1 1 0
*/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1636kb
input:
3 6 7 5 17 4 4
output:
NO YES 3 2 2 4 6 YES 1 1 1 1
result:
ok T=3 (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 1592kb
input:
4194 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 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 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok T=4194 (4194 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 1744kb
input:
1 2 10000000
output:
YES 5000000 5000000
result:
ok T=1 (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 1700kb
input:
1 3 9999999
output:
YES 4999997 4999999 3
result:
ok T=1 (1 test case)
Test #5:
score: 0
Accepted
time: 0ms
memory: 1600kb
input:
1 5 9999999
output:
YES 3 3 4 4999993 4999996
result:
ok T=1 (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 1620kb
input:
1 6 9999999
output:
YES 3 2 2 2 4999995 4999995
result:
ok T=1 (1 test case)
Test #7:
score: 0
Accepted
time: 0ms
memory: 1604kb
input:
1 6 10000000
output:
YES 1 1 1 1 4999998 4999998
result:
ok T=1 (1 test case)
Test #8:
score: 0
Accepted
time: 8ms
memory: 1700kb
input:
20 42 500000 18468 500000 6335 500000 6501 500000 19170 500000 15725 500000 11479 500000 9359 500000 6963 500000 4465 500000 5706 500000 8146 500000 3282 500000 16828 500000 9962 500000 492 500000 2996 500000 11943 500000 4828 500000 5437 500000
output:
YES 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 249980 249980 YES 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 T=20 (20 test cases)
Test #9:
score: 0
Accepted
time: 9ms
memory: 1752kb
input:
20 46 500000 9217 500000 4199 500000 17796 500000 9485 500000 19651 500000 14591 500000 6432 500000 10706 500000 18317 500000 5558 500000 8190 500000 12653 500000 607 500000 12154 500000 17830 500000 9814 500000 10368 500000 6659 500000 8962 500000
output:
YES 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 249978 249978 YES 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 T=20 (20 test cases)
Test #10:
score: 0
Accepted
time: 3ms
memory: 1600kb
input:
5104 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 2 36 2 37 2 38 2 39 2 40 2 41 2 42 2 43 2 44 2 45 2 46 2 47 2 48 2 49 2 50 2 51 2 52 2 53 2 54 2 55 2 56 2 57 2 58 2 59 2 60 2 61 2 6...
output:
YES 1 1 NO YES 2 2 YES 2 3 YES 3 3 NO YES 4 4 YES 4 5 YES 5 5 YES 5 6 YES 6 6 YES 6 7 YES 7 7 NO YES 8 8 YES 8 9 YES 9 9 YES 9 10 YES 10 10 YES 10 11 YES 11 11 YES 11 12 YES 12 12 YES 12 13 YES 13 13 YES 13 14 YES 14 14 YES 14 15 YES 15 15 NO YES 16 16 YES 16 17 YES 17 17 YES 17 18 YES 18 18 YES 18...
result:
ok T=5104 (5104 test cases)
Test #11:
score: 0
Accepted
time: 9ms
memory: 1712kb
input:
33333 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 3 300 ...
output:
YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 150 148 YES 2 ...
result:
ok T=33333 (33333 test cases)