QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331459#3223. Cellular AutomatonKevin5307AC ✓10ms4092kbC++232.1kb2024-02-18 10:30:592024-02-18 10:30:59

Judging History

This is the latest submission verdict.

  • [2024-02-18 10:30:59]
  • Judged
  • Verdict: AC
  • Time: 10ms
  • Memory: 4092kb
  • [2024-02-18 10:30:59]
  • Submitted

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'