-
Notifications
You must be signed in to change notification settings - Fork 0
/
137_D. Problem with Random Tests.cpp
84 lines (71 loc) · 1.57 KB
/
137_D. Problem with Random Tests.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ss string
#define nn "\n"
#define nl "\n"
#define yes cout<<"YES"<<nn
#define no cout<<"NO"<<nn
#define MOD 1000000007
#define pll pair<ll,ll>
#define For(i,x,n) for(ll i=x;i<n;i++)
#define IN1(x); ll x;cin>>x;
#define IN2(x,y); ll x,y;cin>>x>>y;
#define IN3(x,y,z); ll x,y,z;cin>>x>>y>>z;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
string get(string s,string t){
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
string ret(s.size(),'0');
for(ll i =0;i<s.size();i++){
if(s[i]=='1')ret[i] = '1';
if(i<t.size()&&t[i]=='1')ret[i] = '1';
}
reverse(ret.begin(),ret.end());
return ret;
}
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
reverse(s.begin(),s.end());
while(s.size()>0 && s.back()=='0')s.pop_back();
reverse(s.begin(),s.end());
n = s.size();
if(n==0){
cout<<0<<endl;
return;
}
string ans = s;
int m = n;
for(ll i = 0;i<n;i++){
if(s[i]=='1')m--;
else break;
}
for(ll i = 0;i<n;i++){
if(i+m>n)break;
ans = max(ans,get(s,s.substr(i,m)));
}
cout<<ans<<endl;
}
int main ()
{
fastio;
#ifndef ONLINE_JUDGE
freopen ( "input.txt", "r", stdin );
freopen ( "output.txt", "w", stdout );
#endif
ll t = 1;
//cin >> t;
while(t--)
{
solve();
}
printclock
cout.flush();
return 0;
}