#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LBS 20
#define MOD ((ll)(1<<16)+1)//((ll)((1<<24)+(1<<16)+(1<<8)+1))//((long long)1e9+7) //1e9+9
#define PHIMOD ((ll)(1<<16)) //((ll)(1<<24))
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}
using namespace std;
typedef int64_t ll;
typedef double rat;
typedef long long bi;
typedef pair<ll, ll> ii;
typedef std::vector<ii> vii;
typedef std::map<ll, ll> mii;
typedef bitset<LBS> bis;
typedef std::vector<bis> vbs;
typedef array<std::vector<ll>, 4> av; //aa,ab,ba,bb
template<class T>
void in(T &a){
for(auto &x: a)
cin >> x;
}
template<class T>
void out(T &a, string sep=" "){
for(auto x: a)
cout << x<<sep;
cout << '\n';
}
template<class T>
void err(T &a, string sep=" "){
for(auto x: a)
cerr << x <<sep;
cerr << '\n';
}
void fft(std::vector<ll> &v, std::vector<ll> &f, int n, ll a){
std::vector<int> mp(n);
std::vector<ll> pa(n+1);
pa[0]=1;
for(int i=1; i<=n; i++)
pa[i]=(pa[i-1]*a)%MOD;
iota(ALL(mp),0);
sort(ALL(mp),[](const int &a, const int &b){
for(int i=0; i<32; i++)
if((a&(1<<i))!=(b&(1<<i)))
return (a&(1<<i))<(b&(1<<i));
return false;
});
for(int i=0; i<n; i++)
f[i]=v[mp[i]];
ll t;
for(int l=1; l<n; l*=2)
for(int st=0; st<n; st+=l*2)
for(int i=0; i<l; i++){
t=f[st+i];
f[st+i]=(t+(pa[(i*n/l/2)%n]*f[st+i+l])%MOD+MOD)%MOD;
f[st+i+l]=(t+(pa[((i+l)*n/l/2)%n]*f[st+i+l])%MOD+MOD)%MOD;
}
}
ll np2=1, fa, infa;
std::vector<ll> pa;
map<ii,av> miiav;
void rek(const av &a, av &v, int st=0, int l=np2){
if(miiav.count({st,l}))
v=miiav[{st,l}];
if(l==1){
v[0][1]=v[3][0]=1;
return;
}
av lv, rv, lf, rf;
for(int i=0; i<4; i++){
lv[i].resize(l*2,0);
rv[i].resize(l*2,0);
lf[i].resize(l*2,0);
rf[i].resize(l*2,0);
}
rek(a,lv,st,l/2);
rek(a,rv,st+l/2,l/2);
for(int i=0; i<4; i++){
fft(lv[i], lf[i], l*2, pa[np2/l]);
fft(rv[i], rf[i], l*2, pa[np2/l]);
}
av f;
for(int j=0; j<4; j++){
f[j].resize(l*2,0);
for(int k=0; k<4; k++)
if(a[k/2][st+l/2-1]<=a[k%2][st+l/2])
for(int i=0; i<l*2; i++)
f[j][i]+=lf[(j/2)*2+k/2][i]*rf[(k%2)*2+j%2][i];
}
for(int i=0; i<4; i++){
fft(f[i],v[i],l*2, pa[np2*2-np2/l]);
for(auto &x: v[i])
x=(x!=0);
}
miiav[{st,l}]=v;
}
void path(const av &a, string &s, int an, int dir, int st=0, int l=np2){
if(l==1){
assert(dir==0 || dir==3);
s[st]=(dir==0?'A':'B');
return;
}
av lv, rv;
for(int i=0; i<4; i++){
lv[i].resize(l*2);
rv[i].resize(l*2);
}
rek(a,lv,st,l/2);
rek(a,rv,st+l/2,l/2);
for(int k=0; k<4; k++)
if(a[k/2][st+l/2-1]<=a[k%2][st+l/2])
for(int i=max(0,an-l); i<=min(an,l); i++)
if(lv[(dir/2)*2+k/2][i] && rv[(k%2)*2+dir%2][an-i]){
path(a,s,i,(dir/2)*2+k/2,st,l/2);
path(a,s,an-i,(k%2)*2+dir%2,st+l/2,l/2);
return;
}
assert(1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
n*=2;
fa=3;
while(np2<n)
np2*=2;
for(int i=1; i<PHIMOD/np2/2; i*=2)
fa=(fa*fa)%MOD;
// cerr << MOD<<" m "<<PHIMOD<<"\n";
// for(ll i=1; i<PHIMOD; i*=2){
// // if(fa==1){
// cerr << fa <<" "<<i<<"\n";
// // break;
// // }
// fa=(fa*fa)%MOD;
// }
// return 0;
infa=1;
for(int i=1; i<np2*2; i++){
// cerr << i<<" "<<infa<<"\n";
infa=(infa*fa)%MOD;
}
pa.resize(np2*2+1);
pa[0]=1;
for(int i=1; i<=np2*2; i++)
pa[i]=(pa[i-1]*fa)%MOD;
// cerr << fa << " "<<infa<<" f\n";
// return 0;
av a;
for(int i=0; i<2; i++){
a[i].resize(n);
in(a[i]);
a[i].resize(np2);
}
for(int i=n; i<np2; i++){
a[0][i]=a[0][n-1]+a[1][n-1];
a[1][i]=0;
}
av v;
for(int i=0; i<4; i++)
v[i].resize(np2*2);
rek(a,v);
for(int i=0; i<4; i++)
if(v[i][np2-n/2]){
string s(np2,'0');
path(a,s,np2-n/2,i);
cout << s.substr(0,n)<<"\n";
return 0;
}
cout << "-1\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
257 ms |
9464 KB |
Output is correct |
6 |
Correct |
1199 ms |
9568 KB |
Output is correct |
7 |
Correct |
1174 ms |
9464 KB |
Output is correct |
8 |
Correct |
1177 ms |
9468 KB |
Output is correct |
9 |
Correct |
1195 ms |
9592 KB |
Output is correct |
10 |
Correct |
1194 ms |
9592 KB |
Output is correct |
11 |
Correct |
1176 ms |
9596 KB |
Output is correct |
12 |
Correct |
1193 ms |
9720 KB |
Output is correct |
13 |
Correct |
1165 ms |
9592 KB |
Output is correct |
14 |
Correct |
1176 ms |
9720 KB |
Output is correct |
15 |
Correct |
1170 ms |
9592 KB |
Output is correct |
16 |
Correct |
272 ms |
9664 KB |
Output is correct |
17 |
Correct |
1187 ms |
9592 KB |
Output is correct |
18 |
Correct |
1187 ms |
9592 KB |
Output is correct |
19 |
Correct |
1198 ms |
9732 KB |
Output is correct |
20 |
Correct |
1184 ms |
9464 KB |
Output is correct |
21 |
Correct |
1174 ms |
9592 KB |
Output is correct |
22 |
Correct |
1186 ms |
9592 KB |
Output is correct |
23 |
Correct |
1173 ms |
9592 KB |
Output is correct |
24 |
Correct |
1171 ms |
9592 KB |
Output is correct |
25 |
Correct |
1171 ms |
9560 KB |
Output is correct |
26 |
Correct |
1184 ms |
9720 KB |
Output is correct |
27 |
Correct |
1176 ms |
9592 KB |
Output is correct |
28 |
Correct |
1172 ms |
9464 KB |
Output is correct |
29 |
Correct |
1181 ms |
9636 KB |
Output is correct |
30 |
Correct |
1173 ms |
9592 KB |
Output is correct |
31 |
Correct |
1177 ms |
9720 KB |
Output is correct |
32 |
Correct |
1167 ms |
9592 KB |
Output is correct |
33 |
Correct |
1184 ms |
9728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
257 ms |
9464 KB |
Output is correct |
6 |
Correct |
1199 ms |
9568 KB |
Output is correct |
7 |
Correct |
1174 ms |
9464 KB |
Output is correct |
8 |
Correct |
1177 ms |
9468 KB |
Output is correct |
9 |
Correct |
1195 ms |
9592 KB |
Output is correct |
10 |
Correct |
1194 ms |
9592 KB |
Output is correct |
11 |
Correct |
1176 ms |
9596 KB |
Output is correct |
12 |
Correct |
1193 ms |
9720 KB |
Output is correct |
13 |
Correct |
1165 ms |
9592 KB |
Output is correct |
14 |
Correct |
1176 ms |
9720 KB |
Output is correct |
15 |
Correct |
1170 ms |
9592 KB |
Output is correct |
16 |
Correct |
272 ms |
9664 KB |
Output is correct |
17 |
Correct |
1187 ms |
9592 KB |
Output is correct |
18 |
Correct |
1187 ms |
9592 KB |
Output is correct |
19 |
Correct |
1198 ms |
9732 KB |
Output is correct |
20 |
Correct |
1184 ms |
9464 KB |
Output is correct |
21 |
Correct |
1174 ms |
9592 KB |
Output is correct |
22 |
Correct |
1186 ms |
9592 KB |
Output is correct |
23 |
Correct |
1173 ms |
9592 KB |
Output is correct |
24 |
Correct |
1171 ms |
9592 KB |
Output is correct |
25 |
Correct |
1171 ms |
9560 KB |
Output is correct |
26 |
Correct |
1184 ms |
9720 KB |
Output is correct |
27 |
Correct |
1176 ms |
9592 KB |
Output is correct |
28 |
Correct |
1172 ms |
9464 KB |
Output is correct |
29 |
Correct |
1181 ms |
9636 KB |
Output is correct |
30 |
Correct |
1173 ms |
9592 KB |
Output is correct |
31 |
Correct |
1177 ms |
9720 KB |
Output is correct |
32 |
Correct |
1167 ms |
9592 KB |
Output is correct |
33 |
Correct |
1184 ms |
9728 KB |
Output is correct |
34 |
Runtime error |
576 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
35 |
Halted |
0 ms |
0 KB |
- |