QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331459 | #3223. Cellular Automaton | Kevin5307 | AC ✓ | 10ms | 4092kb | C++23 | 2.1kb | 2024-02-18 10:30:59 | 2024-02-18 10:30:59 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int k,m;
vector<pii> G[(1<<12)];
int d[1<<12],c[1<<12];
bool check(string s)
{
for(int i=0;i<m;i++)
G[i].clear();
for(int i=0;i<m;i++)
for(int j=0;j<2;j++)
{
int nxt=((i<<1)|j)&(m-1);
if(nxt<sz(s))
{
int w=j-(s[nxt]^48);
G[i].pb(nxt,w);
G[nxt].pb(i,-w);
}
else
{
G[i].pb(nxt+m,j);
G[nxt+m].pb(i,-j);
}
}
for(int i=sz(s);i<m;i++)
{
G[i+m].pb(i,0);
G[i].pb(i+m,1);
}
memset(d,0x3f,sizeof(d));
memset(c,0,sizeof(c));
d[0]=0;
deque<int> q;
q.push_back(0);
while(!q.empty())
{
int x=q.front();
q.pop_front();
for(auto pr:G[x])
{
int y=pr.first;
int w=pr.second;
if(d[y]>d[x]+w)
{
d[y]=d[x]+w;
c[y]=c[x]+1;
if(c[y]>m+m-sz(s)) return false;
if(!sz(q)||d[y]>d[q.front()])
q.push_back(y);
else
q.push_front(y);
}
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--)
{
cin>>k;
m=(1<<(k+k+1));
string s;
cin>>s;
if(check(s))
cout<<s<<endl;
else
{
int p=-1;
for(int i=m-1;i>=0;i--)
if(s[i]=='0')
if(check(s.substr(0,i)+"1"))
{
p=i;
break;
}
if(p==-1)
{
cout<<"no"<<endl;
continue;
}
string ans=s.substr(0,p)+"1";
for(int i=p+1;i<m;i++)
{
ans+="0";
if(!check(ans))
ans[i]='1';
}
cout<<ans<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
1 11111111
output:
no
result:
ok single line: 'no'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
1 11111101
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
1 11001011
output:
no
result:
ok single line: 'no'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
1 10111110
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
1 10000010
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
1 00100011
output:
00110011
result:
ok single line: '00110011'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
1 01000001
output:
01000111
result:
ok single line: '01000111'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
1 00000100
output:
00001111
result:
ok single line: '00001111'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 01001000
output:
01010101
result:
ok single line: '01010101'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
1 00001000
output:
00001111
result:
ok single line: '00001111'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 00000000
output:
00001111
result:
ok single line: '00001111'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
2 11111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 11111111001111111111111111111110
output:
no
result:
ok single line: 'no'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
2 11111011011111001110111011011101
output:
no
result:
ok single line: 'no'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
2 11011101110111101111111101110111
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
2 11011011111000101011001101110011
output:
no
result:
ok single line: 'no'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
2 00010000010001100111101111101110
output:
00010000010100001101111101011111
result:
ok single line: '00010000010100001101111101011111'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
2 01001010101010011010011000111001
output:
01010000010100000101111101011111
result:
ok single line: '01010000010100000101111101011111'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
2 10001110000000000000010000100001
output:
no
result:
ok single line: 'no'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
2 00100010010010010000001000000101
output:
00100011000000000010111111111111
result:
ok single line: '00100011000000000010111111111111'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
2 00100000000001000000100000000000
output:
00100000000011110010110011111111
result:
ok single line: '00100000000011110010110011111111'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
2 00000000000000000000000000000000
output:
00000000000000001111111111111111
result:
ok single line: '00000000000000001111111111111111'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
3 10101011111111111111111111111111110111111111110011111111111111101111111110111101111111111111111100111111101111101011111110111111
output:
no
result:
ok single line: 'no'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
3 11111100111111101101111111111110111110111111111110101101010111111111111011011111111101110111011101111111010011111111111011011111
output:
no
result:
ok single line: 'no'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 10111110011110010111101011101011111000100110111111001111111011110110010111111001111101010010110000101111111010111111111111011001
output:
no
result:
ok single line: 'no'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
3 11101110111001011110110100001111010111000000010010011001011100111111110011100010011010011011111111010011111110000111010111011100
output:
no
result:
ok single line: 'no'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 10101111000011010011010111111011000100100001101000001011111011101000110101011001110110011010001101111010011101111000011111111101
output:
no
result:
ok single line: 'no'
Test #29:
score: 0
Accepted
time: 8ms
memory: 3764kb
input:
3 00000000000010000000110001000001011101000011001001000001011101000011010000000001000101000000100101100001010011111100001111100000
output:
00000000000010000000110100000000000000100000100000001111111111111111111111111011000011011111000000000010111110111111111111111111
result:
ok single line: '000000000000100000001101000000...0000010111110111111111111111111'
Test #30:
score: 0
Accepted
time: 8ms
memory: 4092kb
input:
3 01000000110100111100001000001001000011100000010101110100001000000010010000110100000001100110001010010000001100000000000001011100
output:
01000001000000000000000000000000000100010000001101010001000000000111110111111111111111111111111111011101111111110101000111111111
result:
ok single line: '010000010000000000000000000000...1011101111111110101000111111111'
Test #31:
score: 0
Accepted
time: 4ms
memory: 4092kb
input:
3 00100010001000100000000000000001100000100000000100000000001010100100000000001000110000000000000000101000000000000000010000000000
output:
00100010001000100000000000000011000001000000000000101100011011110010111011101110000011001111111111110111111111111110111101101111
result:
ok single line: '001000100010001000000000000000...1110111111111111110111101101111'
Test #32:
score: 0
Accepted
time: 10ms
memory: 4080kb
input:
3 00100000000100000010000000010101000000000100000000001100000000000000000000000100100000000001000000000000000000010000010000001000
output:
00100000000100000010000011111111000000000101000000101111011111110010110000010000111011110000000011111111010111111110111101111111
result:
ok single line: '001000000001000000100000111111...1111111010111111110111101111111'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
3 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
result:
ok single line: '000000000000000000000000000000...1111111111111111111111111111111'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 00011101
output:
00011101
result:
ok single line: '00011101'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
1 00011000
output:
00011101
result:
ok single line: '00011101'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 11111111
output:
no
result:
ok single line: 'no'