QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235736 | #3223. Cellular Automaton | Mobius_127 | AC ✓ | 14ms | 59128kb | C++14 | 2.0kb | 2023-11-03 07:58:22 | 2023-11-03 07:58:23 |
Judging History
answer
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#define pb push_back
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=1e9+7;
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int ksm(int a, int b){
int ret=1;
for(; b; b>>=1, a=1ll*a*a%cp)
if(b&1) ret=1ll*ret*a%cp;
return ret;
}
const int N=(1<<21);
int n, K, dis[N], vis[N];
char s[N];
vector <Pii> G[N];
queue <int> Q;
void clear(){
for(int i=0; i<=(n>>1); ++i)
G[i].clear(), vis[i]=0, dis[i]=INF;
while(!Q.empty()) Q.pop();
}
bool SPFA(int S){
Q.push(S);dis[S]=0;
while(!Q.empty()){
int x=Q.front();Q.pop();vis[x]=0;
for(auto v:G[x])
if(dis[v.st]>dis[x]+v.nd){
dis[v.st]=dis[x]+v.nd;
if(!vis[v.st]){
vis[v.st]=1, Q.push(v.st);
if(dis[0]<0) return 0;
}
}
}
return 1;
}
bool check(int state){
clear();
G[0].pb({n>>1, 0}), G[n>>1].pb({0,0});
for(int S=0; S<(n>>1); ++S)
for(int bit=0; bit<2; ++bit){
int T=S|(bit<<(K<<1)), nxt=T>>1, type=T>>K&1;
int x=1-type, y=type;
if(T<state) x=(s[T]=='1')-type, y=type-(s[T]=='1');
G[nxt].pb({S, x}), G[S].pb({nxt, y});
}
return SPFA(n>>1);
}
void solve(){
K=read();scanf("%s", s);n=1<<(K<<1|1);
int pos=n;
if(!check(pos)){
for(pos=n-1; pos>=0; --pos)
if(s[pos]=='0'){
s[pos]='1';
if(check(pos+1)) break;
}
}
if(pos<0){
puts("no");
return ;
}
for(++pos; pos<n; ++pos){
s[pos]='0';
if(!check(pos+1)) s[pos]='1';
}
for(int i=0; i<n; ++i) putchar(s[i]);puts("");
}
signed main(){
int T=1;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 9ms
memory: 57820kb
input:
1 11111111
output:
no
result:
ok single line: 'no'
Test #2:
score: 0
Accepted
time: 3ms
memory: 57936kb
input:
1 11111101
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 9ms
memory: 58924kb
input:
1 11001011
output:
no
result:
ok single line: 'no'
Test #4:
score: 0
Accepted
time: 0ms
memory: 57976kb
input:
1 10111110
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 9ms
memory: 58824kb
input:
1 10000010
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 3ms
memory: 57692kb
input:
1 00100011
output:
00110011
result:
ok single line: '00110011'
Test #7:
score: 0
Accepted
time: 7ms
memory: 57292kb
input:
1 01000001
output:
01000111
result:
ok single line: '01000111'
Test #8:
score: 0
Accepted
time: 3ms
memory: 57156kb
input:
1 00000100
output:
00001111
result:
ok single line: '00001111'
Test #9:
score: 0
Accepted
time: 14ms
memory: 58140kb
input:
1 01001000
output:
01010101
result:
ok single line: '01010101'
Test #10:
score: 0
Accepted
time: 0ms
memory: 58460kb
input:
1 00001000
output:
00001111
result:
ok single line: '00001111'
Test #11:
score: 0
Accepted
time: 6ms
memory: 58024kb
input:
1 00000000
output:
00001111
result:
ok single line: '00001111'
Test #12:
score: 0
Accepted
time: 9ms
memory: 57812kb
input:
2 11111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 11ms
memory: 58296kb
input:
2 11111111001111111111111111111110
output:
no
result:
ok single line: 'no'
Test #14:
score: 0
Accepted
time: 3ms
memory: 59128kb
input:
2 11111011011111001110111011011101
output:
no
result:
ok single line: 'no'
Test #15:
score: 0
Accepted
time: 3ms
memory: 58040kb
input:
2 11011101110111101111111101110111
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 9ms
memory: 57428kb
input:
2 11011011111000101011001101110011
output:
no
result:
ok single line: 'no'
Test #17:
score: 0
Accepted
time: 7ms
memory: 58420kb
input:
2 00010000010001100111101111101110
output:
00010000010100001101111101011111
result:
ok single line: '00010000010100001101111101011111'
Test #18:
score: 0
Accepted
time: 0ms
memory: 58284kb
input:
2 01001010101010011010011000111001
output:
01010000010100000101111101011111
result:
ok single line: '01010000010100000101111101011111'
Test #19:
score: 0
Accepted
time: 7ms
memory: 57840kb
input:
2 10001110000000000000010000100001
output:
no
result:
ok single line: 'no'
Test #20:
score: 0
Accepted
time: 4ms
memory: 58704kb
input:
2 00100010010010010000001000000101
output:
00100011000000000010111111111111
result:
ok single line: '00100011000000000010111111111111'
Test #21:
score: 0
Accepted
time: 0ms
memory: 58324kb
input:
2 00100000000001000000100000000000
output:
00100000000011110010110011111111
result:
ok single line: '00100000000011110010110011111111'
Test #22:
score: 0
Accepted
time: 7ms
memory: 57708kb
input:
2 00000000000000000000000000000000
output:
00000000000000001111111111111111
result:
ok single line: '00000000000000001111111111111111'
Test #23:
score: 0
Accepted
time: 4ms
memory: 57904kb
input:
3 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
output:
no
result:
ok single line: 'no'
Test #24:
score: 0
Accepted
time: 6ms
memory: 57400kb
input:
3 10101011111111111111111111111111110111111111110011111111111111101111111110111101111111111111111100111111101111101011111110111111
output:
no
result:
ok single line: 'no'
Test #25:
score: 0
Accepted
time: 9ms
memory: 57572kb
input:
3 11111100111111101101111111111110111110111111111110101101010111111111111011011111111101110111011101111111010011111111111011011111
output:
no
result:
ok single line: 'no'
Test #26:
score: 0
Accepted
time: 0ms
memory: 58280kb
input:
3 10111110011110010111101011101011111000100110111111001111111011110110010111111001111101010010110000101111111010111111111111011001
output:
no
result:
ok single line: 'no'
Test #27:
score: 0
Accepted
time: 10ms
memory: 58876kb
input:
3 11101110111001011110110100001111010111000000010010011001011100111111110011100010011010011011111111010011111110000111010111011100
output:
no
result:
ok single line: 'no'
Test #28:
score: 0
Accepted
time: 7ms
memory: 56920kb
input:
3 10101111000011010011010111111011000100100001101000001011111011101000110101011001110110011010001101111010011101111000011111111101
output:
no
result:
ok single line: 'no'
Test #29:
score: 0
Accepted
time: 4ms
memory: 57588kb
input:
3 00000000000010000000110001000001011101000011001001000001011101000011010000000001000101000000100101100001010011111100001111100000
output:
00000000000010000000110100000000000000100000100000001111111111111111111111111011000011011111000000000010111110111111111111111111
result:
ok single line: '000000000000100000001101000000...0000010111110111111111111111111'
Test #30:
score: 0
Accepted
time: 7ms
memory: 58480kb
input:
3 01000000110100111100001000001001000011100000010101110100001000000010010000110100000001100110001010010000001100000000000001011100
output:
01000001000000000000000000000000000100010000001101010001000000000111110111111111111111111111111111011101111111110101000111111111
result:
ok single line: '010000010000000000000000000000...1011101111111110101000111111111'
Test #31:
score: 0
Accepted
time: 7ms
memory: 58888kb
input:
3 00100010001000100000000000000001100000100000000100000000001010100100000000001000110000000000000000101000000000000000010000000000
output:
00100010001000100000000000000011000001000000000000101100011011110010111011101110000011001111111111110111111111111110111101101111
result:
ok single line: '001000100010001000000000000000...1110111111111111110111101101111'
Test #32:
score: 0
Accepted
time: 4ms
memory: 58844kb
input:
3 00100000000100000010000000010101000000000100000000001100000000000000000000000100100000000001000000000000000000010000010000001000
output:
00100000000100000010000011111111000000000101000000101111011111110010110000010000111011110000000011111111010111111110111101111111
result:
ok single line: '001000000001000000100000111111...1111111010111111110111101111111'
Test #33:
score: 0
Accepted
time: 7ms
memory: 57236kb
input:
3 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
result:
ok single line: '000000000000000000000000000000...1111111111111111111111111111111'
Test #34:
score: 0
Accepted
time: 9ms
memory: 57396kb
input:
1 00011101
output:
00011101
result:
ok single line: '00011101'
Test #35:
score: 0
Accepted
time: 3ms
memory: 58848kb
input:
1 00011000
output:
00011101
result:
ok single line: '00011101'
Test #36:
score: 0
Accepted
time: 3ms
memory: 58552kb
input:
1 11111111
output:
no
result:
ok single line: 'no'