Submission #3234905
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define sqr(x) ((x)*(x)) #define mp make_pair #define uint unsigned #define ld long double #define PI pair<int,int> inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } #define gc getchar inline ll read(){ ll x = 0; char ch = gc(); bool positive = 1; for (; !isdigit(ch); ch = gc()) if (ch == '-') positive = 0; for (; isdigit(ch); ch = gc()) x = x * 10 + ch - '0'; return positive ? x : -x; } inline void write(ll a){ if(a<0){ a=-a; putchar('-'); } if(a>=10)write(a/10); putchar('0'+a%10); } inline void writeln(ll a){write(a); puts("");} inline void wri(ll a){write(a); putchar(' ');} inline ull rnd(){ return ((ull)rand()<<30^rand())<<4|rand()%4; } const int N=22,M=1<<21|5; int n,k,dp[N][M],ycl[M],Ans[M]; char ch[M]; inline int lowbit(int x){ return x&(-x); } int rev(int x,int len){ for(int i=0;i<len/2;i++){ int a=x>>i&1,b=x>>(len-i-1)&1; x^=(a^b)<<i; x^=(a^b)<<(len-i-1); } return x; } signed main(){ n=read(); k=read(); for(int i=0;i<=n;i++){ scanf("%s",ch); for(int j=0;j<(1<<i);j++)dp[0][(1<<i)+j]+=ch[j]-'0'; } for(int i=2;i<(1<<(n+1));i++)ycl[i]=ycl[i>>1]+1; for(int i=0;i<n;i++){ for(int j=1<<(i+1);j<(1<<(n+1));j++)if(dp[i][j]){ //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; int len=ycl[j],t=j-(1<<len),k=t>>i; if(j>>i&1){ dp[i+1][j]+=dp[i][j]; //if(i==0&&j==13)cout<<k<<" "<<(k>>ycl[lowbit(k^((1<<len)-1))]|(t&((1<<i)-1)))<<endl; if(k^((1<<len)-1))dp[i+1][(1<<(len-ycl[lowbit(k^((1<<len)-1))]))+((k>>ycl[lowbit(k^((1<<len)-1))])<<i|(t&((1<<i)-1)))]+=dp[i][j]; }else{ dp[i+1][j]+=dp[i][j]; //if(i==1&&j==12)cout<<k<<" "<<(1<<(len-ycl[lowbit(k)]))+(k>>ycl[lowbit(k)]|(t&((1<<i)-1)))<<endl; if(k)dp[i+1][(1<<(len-ycl[lowbit(k)]))+((k>>ycl[lowbit(k)])<<i|(t&((1<<i)-1)))]+=dp[i][j]; } } } for(int i=0;i<=n;i++){ for(int j=1<<i;j<(1<<(n+1));j++){ int t=j-(1<<ycl[j]); Ans[(1<<i)+(t&((1<<i)-1))]+=dp[i][j]; } } //cout<<dp[1][6]<<" "<<dp[2][6]<<" "<<dp[2][10]<<" "<<dp[2][14]<<" "<<Ans[6]<<endl; for(int i=(1<<(n+1))-1;i;i--)if(Ans[i]>=k){ for(int j=1<<ycl[i];j<(1<<(ycl[i]+1));j++){ int jj=j-(1<<ycl[j]),t=rev(jj,ycl[j]); if(Ans[t+(1<<ycl[j])]>=k){ for(int o=0;o<ycl[j];o++)write(jj>>o&1); return 0; } } } } /* 3 3 1 01 1011 01001110 */
Submission Info
Submission Time | |
---|---|
Task | F - Simple Subsequence Problem |
User | wzp |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2537 Byte |
Status | WA |
Exec Time | 389 ms |
Memory | 191872 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:49:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",ch); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 2300 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, 89.txt, 90.txt, 91.txt, 92.txt, 93.txt, 94.txt, 95.txt, 96.txt, 97.txt, 98.txt, 99.txt, A0.txt, A1.txt, A2.txt, A3.txt, A4.txt, A5.txt, A6.txt, A7.txt, A8.txt, A9.txt, B0.txt, B1.txt, B2.txt, B3.txt, B4.txt, B5.txt, B6.txt, B7.txt, B8.txt, B9.txt, C0.txt, C1.txt, C2.txt, C3.txt, C4.txt, C5.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | WA | 382 ms | 189696 KB |
02.txt | WA | 389 ms | 189696 KB |
03.txt | AC | 373 ms | 189696 KB |
04.txt | WA | 278 ms | 189696 KB |
05.txt | AC | 276 ms | 189696 KB |
06.txt | AC | 276 ms | 189696 KB |
07.txt | AC | 345 ms | 189696 KB |
08.txt | WA | 345 ms | 189696 KB |
09.txt | AC | 345 ms | 189696 KB |
10.txt | WA | 174 ms | 189696 KB |
11.txt | WA | 172 ms | 189696 KB |
12.txt | AC | 175 ms | 188928 KB |
13.txt | AC | 338 ms | 189696 KB |
14.txt | WA | 337 ms | 189696 KB |
15.txt | AC | 337 ms | 189824 KB |
16.txt | AC | 338 ms | 189696 KB |
17.txt | AC | 337 ms | 189696 KB |
18.txt | AC | 338 ms | 189696 KB |
19.txt | AC | 364 ms | 189696 KB |
20.txt | AC | 364 ms | 189696 KB |
21.txt | AC | 363 ms | 189696 KB |
22.txt | WA | 338 ms | 189696 KB |
23.txt | WA | 333 ms | 191744 KB |
24.txt | WA | 329 ms | 191744 KB |
25.txt | AC | 336 ms | 191744 KB |
26.txt | AC | 307 ms | 191744 KB |
27.txt | AC | 322 ms | 191744 KB |
28.txt | AC | 148 ms | 142592 KB |
29.txt | AC | 337 ms | 191744 KB |
30.txt | AC | 336 ms | 191744 KB |
31.txt | AC | 371 ms | 191744 KB |
32.txt | AC | 371 ms | 191744 KB |
33.txt | AC | 372 ms | 191744 KB |
34.txt | AC | 275 ms | 191744 KB |
35.txt | WA | 277 ms | 191744 KB |
36.txt | AC | 261 ms | 191744 KB |
37.txt | WA | 216 ms | 191744 KB |
38.txt | WA | 281 ms | 191744 KB |
39.txt | WA | 208 ms | 191744 KB |
40.txt | WA | 204 ms | 191744 KB |
41.txt | AC | 166 ms | 187648 KB |
42.txt | WA | 154 ms | 191744 KB |
43.txt | AC | 276 ms | 191744 KB |
44.txt | AC | 331 ms | 191744 KB |
45.txt | WA | 282 ms | 191744 KB |
46.txt | AC | 336 ms | 191744 KB |
47.txt | AC | 312 ms | 191744 KB |
48.txt | AC | 274 ms | 191744 KB |
49.txt | WA | 216 ms | 191744 KB |
50.txt | AC | 193 ms | 191744 KB |
51.txt | AC | 360 ms | 191744 KB |
52.txt | AC | 329 ms | 191744 KB |
53.txt | AC | 312 ms | 191744 KB |
54.txt | AC | 146 ms | 146688 KB |
55.txt | AC | 4 ms | 16640 KB |
56.txt | AC | 3 ms | 8448 KB |
57.txt | WA | 371 ms | 191744 KB |
58.txt | AC | 5 ms | 20736 KB |
59.txt | AC | 4 ms | 12544 KB |
60.txt | WA | 45 ms | 41344 KB |
61.txt | AC | 4 ms | 14592 KB |
62.txt | AC | 4 ms | 14592 KB |
63.txt | AC | 45 ms | 41344 KB |
64.txt | AC | 5 ms | 18688 KB |
65.txt | AC | 4 ms | 12544 KB |
66.txt | AC | 6 ms | 22784 KB |
67.txt | AC | 5 ms | 20736 KB |
68.txt | AC | 152 ms | 142592 KB |
69.txt | AC | 150 ms | 146688 KB |
70.txt | AC | 162 ms | 140672 KB |
71.txt | AC | 156 ms | 142592 KB |
72.txt | AC | 141 ms | 140544 KB |
73.txt | AC | 148 ms | 185600 KB |
74.txt | AC | 5 ms | 22784 KB |
75.txt | AC | 8 ms | 33024 KB |
76.txt | WA | 345 ms | 191744 KB |
77.txt | WA | 306 ms | 191744 KB |
78.txt | AC | 268 ms | 191744 KB |
79.txt | AC | 346 ms | 191744 KB |
80.txt | AC | 342 ms | 191744 KB |
81.txt | AC | 304 ms | 191744 KB |
82.txt | AC | 356 ms | 191744 KB |
83.txt | AC | 374 ms | 191744 KB |
84.txt | AC | 272 ms | 191744 KB |
85.txt | AC | 244 ms | 191744 KB |
86.txt | WA | 347 ms | 191744 KB |
87.txt | AC | 306 ms | 191744 KB |
88.txt | AC | 344 ms | 191744 KB |
89.txt | AC | 339 ms | 191744 KB |
90.txt | AC | 296 ms | 191744 KB |
91.txt | AC | 337 ms | 191744 KB |
92.txt | AC | 315 ms | 191744 KB |
93.txt | AC | 260 ms | 191744 KB |
94.txt | AC | 364 ms | 191744 KB |
95.txt | AC | 216 ms | 191744 KB |
96.txt | AC | 345 ms | 191744 KB |
97.txt | AC | 366 ms | 191744 KB |
98.txt | AC | 330 ms | 191744 KB |
99.txt | WA | 373 ms | 191744 KB |
A0.txt | AC | 351 ms | 191744 KB |
A1.txt | AC | 350 ms | 191744 KB |
A2.txt | AC | 358 ms | 191744 KB |
A3.txt | AC | 335 ms | 191744 KB |
A4.txt | AC | 364 ms | 191744 KB |
A5.txt | AC | 360 ms | 191744 KB |
A6.txt | AC | 369 ms | 191872 KB |
A7.txt | AC | 352 ms | 191744 KB |
A8.txt | AC | 355 ms | 191744 KB |
A9.txt | AC | 349 ms | 191744 KB |
B0.txt | WA | 216 ms | 191744 KB |
B1.txt | AC | 370 ms | 191744 KB |
B2.txt | AC | 340 ms | 191744 KB |
B3.txt | AC | 339 ms | 191744 KB |
B4.txt | AC | 372 ms | 191744 KB |
B5.txt | AC | 299 ms | 191744 KB |
B6.txt | AC | 372 ms | 191744 KB |
B7.txt | AC | 306 ms | 191744 KB |
B8.txt | AC | 372 ms | 191744 KB |
B9.txt | WA | 341 ms | 191744 KB |
C0.txt | AC | 175 ms | 191744 KB |
C1.txt | AC | 3 ms | 8448 KB |
C2.txt | AC | 2 ms | 4352 KB |
C3.txt | AC | 3 ms | 8448 KB |
C4.txt | AC | 3 ms | 8448 KB |
C5.txt | AC | 3 ms | 8448 KB |
s1.txt | AC | 4 ms | 12544 KB |
s2.txt | AC | 4 ms | 14592 KB |
s3.txt | AC | 3 ms | 10496 KB |