QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #369431 | #8174. Set Construction | Doqe | WA | 11ms | 28932kb | C++14 | 1.9kb | 2024-03-28 09:09:13 | 2024-03-28 09:09:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<long long>up[63][63*63];
int via[63][63*63];
vector<long long>solve(int n,int m)
{
// cerr<<"SOLVE: "<<n<<" "<<m<<endl;
if(!(n>=1&&m>=2&&m<=(1ll<<n)))return //cerr<<n<<","<<m<<" FAILED\n",
vector<long long>();
assert(n>=1&&m>=2&&m<=(1ll<<n));
if(m==2)return {0ll,(1ll<<n)-1};
if(m==3)return {0ll,1ll,(1ll<<n)-1};
if(via[n][m])return //cerr<<n<<","<<m<<" SUC\n",
up[n][m];
via[n][m]=1;
// if(m==4)return {0ll,1ll,(1ll<<n)-1^1,(1ll<<n)-1};
for(int S=1;(1<<S)-1<=m-2&&S<=n-1;++S)
{
// cerr<<S<<" : "<<m-(1<<S)+1<<" "<<n-S<<endl;
vector<long long>X=solve(n-S,m-(1<<S)+1);
if(X.empty())continue;
vector<long long>A;
for(int i=0;i<(1<<S)-1;++i)A.push_back(i);
for(auto k:X)A.push_back((k<<S)|((1<<S)-1));
// cerr<<n<<","<<m<<"SUC\n";
return up[n][m]=A;
}
if(m%2==0)
{
vector<long long>X=solve(n-1,m/2);
if(X.size())
{
vector<long long>A;
for(auto k:X)A.push_back(k);
for(auto k:X)A.push_back(k|(1ll<<n-1));
// cerr<<n<<","<<m<<"SUC\n";
return up[n][m]=A;
}
}
// cerr<<n<<","<<m<<" FAILED\n";
return vector<long long>();
}
bool judge(vector<long long>X)
{
set<long long>S;
for(auto k:X)S.insert(k);
for(auto k:X)
for(auto t:X)if(S.find(k&t)!=S.end()&&S.find(k|t)!=S.end());
else return false;
return true;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int T,n,m;cin>>T;
// for(int i=2;i<=60;++i)
// for(int j=2;j<=i*(i+1)/2;++j)
// {
//// cerr<<"SOL: "<<i<<" "<<j<<endl;
// auto w=solve(i,j);
//// assert(w.size());
// if(!w.size())cerr<<"WA: "<<i<<" , "<<j<<endl;
// }
// up[5][15]={0,2,3,4,6,7,8,10,11,12,14,15,28,30,31};
// for(int i=2;i<=60;++i)
// for(int j=2;j<=i*(i+1)/2;++j)
// cerr<<"JUDGE: "<<i<<" "<<j<<endl,
// assert(judge(up[i][j]));
while(T--)
{
cin>>n>>m;vector<long long>X=solve(n,m);
for(auto i:X)cout<<i<<" ";cout<<endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 10096kb
input:
3 3 5 4 8 60 2
output:
0 1 3 5 7 0 1 3 7 8 9 11 15 0 1152921504606846975
result:
ok AC
Test #2:
score: 0
Accepted
time: 2ms
memory: 10156kb
input:
30 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 6 20 6 21 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11
output:
0 63 0 1 63 0 1 3 63 0 1 3 7 63 0 1 3 7 15 63 0 1 3 7 15 31 63 0 1 3 7 15 31 47 63 0 1 3 7 15 31 39 47 63 0 1 3 7 15 31 35 39 47 63 0 1 3 7 15 23 31 39 47 55 63 0 1 3 7 15 23 31 35 39 47 55 63 0 1 3 7 15 23 31 33 35 39 47 55 63 0 1 3 7 15 19 23 31 35 39 47 51 55 63 0 1 3 7 15 19 23 31 3...
result:
ok AC
Test #3:
score: 0
Accepted
time: 2ms
memory: 9452kb
input:
30 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 7 20 7 21 7 22 7 23 7 24 7 25 7 26 7 27 7 28 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 8 12 8 13 8 14
output:
0 1 3 7 15 31 47 63 79 95 111 127 0 1 3 7 15 31 47 63 71 79 95 111 127 0 1 3 7 15 31 47 63 67 71 79 95 111 127 0 1 3 7 15 31 39 47 63 71 79 95 103 111 127 0 1 3 7 15 31 39 47 63 67 71 79 95 103 111 127 0 1 3 7 15 31 39 47 63 65 67 71 79 95 103 111 127 0 1 3 7 15 31 35 39 47 63 67 71 79 95 99 1...
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 9472kb
input:
30 8 15 8 16 8 17 8 18 8 19 8 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 8 31 8 32 8 33 8 34 8 35 8 36 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9
output:
0 1 3 7 15 31 63 95 127 135 143 159 191 223 255 0 1 3 7 15 31 63 79 95 127 143 159 191 207 223 255 0 1 3 7 15 31 63 79 95 127 135 143 159 191 207 223 255 0 1 3 7 15 31 63 79 95 127 131 135 143 159 191 207 223 255 0 1 3 7 15 31 63 71 79 95 127 135 143 159 191 199 207 223 255 0 1 3 7 15 31 47 63 ...
result:
ok AC
Test #5:
score: 0
Accepted
time: 2ms
memory: 9480kb
input:
30 9 10 9 11 9 12 9 13 9 14 9 15 9 16 9 17 9 18 9 19 9 20 9 21 9 22 9 23 9 24 9 25 9 26 9 27 9 28 9 29 9 30 9 31 9 32 9 33 9 34 9 35 9 36 9 37 9 38 9 39
output:
0 1 3 7 15 31 63 127 255 511 0 1 3 7 15 31 63 127 255 383 511 0 1 3 7 15 31 63 127 255 319 383 511 0 1 3 7 15 31 63 127 255 287 319 383 511 0 1 3 7 15 31 63 127 191 255 319 383 447 511 0 1 3 7 15 31 63 127 191 255 287 319 383 447 511 0 1 3 7 15 31 63 127 191 255 271 287 319 383 447 511 0 1 3 ...
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 9848kb
input:
6 9 40 9 41 9 42 9 43 9 44 9 45
output:
0 1 3 7 15 31 47 63 79 95 111 127 135 143 159 175 191 207 223 239 255 259 263 271 287 303 319 335 351 367 383 391 399 415 431 447 463 479 495 511 0 1 3 7 15 31 47 63 79 95 111 127 135 143 159 175 191 207 223 239 255 257 259 263 271 287 303 319 335 351 367 383 391 399 415 431 447 463 479 495 511 0 ...
result:
ok AC
Test #7:
score: 0
Accepted
time: 11ms
memory: 28932kb
input:
30 60 1801 60 1802 60 1803 60 1804 60 1805 60 1806 60 1807 60 1808 60 1809 60 1810 60 1811 60 1812 60 1813 60 1814 60 1815 60 1816 60 1817 60 1818 60 1819 60 1820 60 1821 60 1822 60 1823 60 1824 60 1825 60 1826 60 1827 60 1828 60 1829 60 1830
output:
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 1073741823 2147483647 4294967295 8589934591 17179869183 34359738367 68719476735 137438953471 274877906943 549755813887 1099...
result:
ok AC
Test #8:
score: 0
Accepted
time: 7ms
memory: 28672kb
input:
30 59 1741 59 1742 59 1743 59 1744 59 1745 59 1746 59 1747 59 1748 59 1749 59 1750 59 1751 59 1752 59 1753 59 1754 59 1755 59 1756 59 1757 59 1758 59 1759 59 1760 59 1761 59 1762 59 1763 59 1764 59 1765 59 1766 59 1767 59 1768 59 1769 59 1770
output:
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 1073741823 2147483647 4294967295 8589934591 17179869183 34359738367 68719476735 137438953471 274877906943 549755813887 1099...
result:
ok AC
Test #9:
score: 0
Accepted
time: 10ms
memory: 27556kb
input:
30 58 1682 58 1683 58 1684 58 1685 58 1686 58 1687 58 1688 58 1689 58 1690 58 1691 58 1692 58 1693 58 1694 58 1695 58 1696 58 1697 58 1698 58 1699 58 1700 58 1701 58 1702 58 1703 58 1704 58 1705 58 1706 58 1707 58 1708 58 1709 58 1710 58 1711
output:
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 1073741823 2147483647 4294967295 8589934591 17179869183 34359738367 68719476735 137438953471 274877906943 549755813887 1099...
result:
ok AC
Test #10:
score: -100
Wrong Answer
time: 3ms
memory: 9428kb
input:
30 2 2 2 3 3 2 3 3 3 4 3 5 3 6 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15
output:
0 3 0 1 3 0 7 0 1 7 0 1 3 7 0 1 3 5 7 0 1 3 4 5 7 0 15 0 1 15 0 1 3 15 0 1 3 7 15 0 1 3 7 11 15 0 1 3 7 9 11 15 0 1 3 7 8 9 11 15 0 1 3 5 7 9 11 13 15 0 1 3 5 7 8 9 11 13 15 0 31 0 1 31 0 1 3 31 0 1 3 7 31 0 1 3 7 15 31 0 1 3 7 15 23 31 0 1 3 7 15 19 23 31 0 1 3 7 15 17 19 23 ...
result:
wrong output format Unexpected end of file - int64 expected