QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331457 | #3223. Cellular Automaton | Kevin5307 | WA | 1ms | 3612kb | C++23 | 2.1kb | 2024-02-18 10:30:31 | 2024-02-18 10:30:32 |
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<<p<<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;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3612kb
input:
1 11111111
output:
-1
result:
wrong answer 1st lines differ - expected: 'no', found: '-1'