This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mars.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=42;
vector<int>decrypt(string s,int sz,string t){
vector<int>ans;
vector<int>st;
int cnt=0;
for (int i=0;i<100 && ans.size()<sz;i+=2){
if (s[i]=='0' && s[i+1]=='0') break;
else if (s[i]=='1' && s[i+1]=='0'){
cnt++;
st.push_back(cnt);
ans.push_back(cnt);
} else if (s[i]=='1' && s[i+1]=='1'){
ans.push_back(st.back());
} else if (s[i]=='0' && s[i+1]=='1'){
st.pop_back();
}
}
vector<int>rl(t.size(),0);
int ind=0;
for (int i=0;i<t.size();i++){
if (t[i]=='1'){
int j=i;
while (j+1<t.size() && t[j+1]=='1') j++;
while (i<=j){
rl[i++]=ans[ind];
}
ind++;
i=i-1;
}
}
return rl;
}
int dsu[N][N];
int CNT=0;
const int Lg=11;
int go[N*N];
bool used[N*N];
int get(int x){
if (!x) return 0;
if (go[x]==x) return x;
return go[x]=get(go[x]);
}
void unite(int x,int y){
x=get(x);
y=get(y);
if (x!=y){
CNT--;
go[x]=y;
}
}
string process(vector<vector<string>> a, int i, int j, int k, int n)
{
// cout<<i<<" "<<j<<" "<<k<<" "<<n<<endl;
k*=2;
n=2*n;
if (i+k+2==n && j+k+2==n){
if (k==0){
memset(dsu,0,sizeof(dsu));
int mx=0;
for (int x=0;x<3;x++){
for (int y=0;y<3;y++){
if (a[x][y][0]=='1') dsu[i+x][j+y]=++mx;
}
}
for (int i=1;i<=mx;i++) go[i]=i,used[i]=false;
CNT=mx;
for (int i=0;i<Lg;i++){
if (a[2][2][100-i-1]=='1') CNT+=(1<<i);
}
for (int x=i;x<=n;x++){
for (int y=j;y<=n;y++){
for (int dx=-1;dx<=1;dx++){
for (int dy=-1;dy<=1;dy++){
if (!dx && !dy) continue;
if (dx && dy) continue;
int nx=x+dx;
int ny=y+dy;
if (!dsu[x][y]) continue;
if (!dsu[nx][ny]) continue;
unite(dsu[x][y],dsu[nx][ny]);
}
}
}
}
string ans="";
if (k<n-2){
vector<int>message;
for (int x=n;x>=i;x--){
message.push_back(get(dsu[x][j]));
}
for (int y=j+1;y<=n;y++){
message.push_back(get(dsu[i][y]));
}
vector<int>nw;
for (int i=0;i<message.size();i++){
if (!message[i]) continue;
if (i==0 || message[i]!=message[i-1]) nw.push_back(message[i]);
}
message=nw;
// cerr<<"OOOOOO"<<endl;
vector<int>st;
for (int i:message){
if (!used[i]){
used[i]=true;
ans+="10";
st.push_back(i);
} else {
while (st.back()!=i){
ans+="01";
st.pop_back();
}
ans+="11";
// st.push_back(i);
}
}
if (ans.size()+Lg>100){
while (true){
ans+="0";
}
}
while (ans.size()<100) ans+="0";
for (int i=0;i<Lg;i++){
if (CNT&(1<<i)){
ans[100-i-1]='1';
}
}
} else {
for (int i=0;i<100;i++) ans+="0";
for (int i=0;i<Lg;i++){
if (CNT&(1<<i)) ans[i]='1';
}
}
// cout<<"AAAAAAAA "<<ans.size()<<endl;
return ans;
} else {
memset(dsu,0,sizeof(dsu));
string s="";
for (int x=n;x>=i+2;x--){
s+=a[2][1][n+(x-i-2)];
}
for (int y=j+3;y<=n;y++){
s+=a[1][2][n+y-j-2];
}
// cout<<s<<endl;
vector<int>v=decrypt(a[2][2],2*k+1,s);
// cout<<a[2][2]<<endl;
// cout<<"V "<<2*k+1<<" ";
// for (int i:v) cout<<i<<" ";
// cout<<endl;
int mx=0;
for (int i:v) mx=max(mx,i);
int last=mx;
for (int x=n;x>=j+2;x--){
dsu[i+2][x]=v.back();
v.pop_back();
}
for (int y=i+3;y<=n;y++){
dsu[y][j+2]=v.back();
v.pop_back();
}
if (a[0][0][0]=='1') dsu[i][j]=(++mx);
if (a[0][1][0]=='1') dsu[i][j+1]=(++mx);
if (a[1][0][0]=='1') dsu[i+1][j]=(++mx);
if (a[1][1][0]=='1') dsu[i+1][j+1]=(++mx);
for (int x=i+2;x<=n;x++){
if (a[2][0][x-i-2]=='1') dsu[x][j]=(++mx);
}
for (int x=i+2;x<=n;x++){
if (a[2][1][x-i-2]=='1') dsu[x][j+1]=(++mx);
}
for (int x=j+2;x<=n;x++){
if (a[0][2][x-i-2]=='1') dsu[i][x]=(++mx);
}
for (int x=j+2;x<=n;x++){
if (a[1][2][x-i-2]=='1') dsu[i+1][x]=(++mx);
}
for (int i=1;i<=mx;i++) go[i]=i,used[i]=false;
CNT=mx-last;
for (int x=0;x<Lg;x++){
if (a[2][2][100-x-1]=='1') CNT+=(1<<x);
}
// cerr<<"OOOOOO"<<endl;
// for (int x=0;x<=n;x++){
// for (int y=0;y<=n;y++){
// cout<<dsu[x][y]<<" ";
// }
// cout<<endl;
// }
for (int x=i;x<=n;x++){
for (int y=j;y<=n;y++){
for (int dx=-1;dx<=1;dx++){
for (int dy=-1;dy<=1;dy++){
if (!dx && !dy) continue;
if (dx && dy) continue;
int nx=x+dx;
int ny=y+dy;
if (nx<0 || nx>n || ny<0 || ny>n) continue;
if (!dsu[x][y]) continue;
if (!dsu[nx][ny]) continue;
// cout<<x<<" "<<y<<" "<<nx<<" "<<ny<<" "<<dsu[x][y]<<" "<<dsu[nx][ny]<<endl;
unite(dsu[x][y],dsu[nx][ny]);
}
}
}
}
// cerr<<"OOOOOO"<<endl;
vector<int>message;
for (int x=n;x>=i;x--){
message.push_back(get(dsu[x][j]));
}
for (int y=j+1;y<=n;y++){
message.push_back(get(dsu[i][y]));
}
vector<int>nw;
for (int i=0;i<message.size();i++){
if (!message[i]) continue;
if (i==0 || message[i]!=message[i-1]) nw.push_back(message[i]);
}
message=nw;
string ans="";
if (k<n-2){
// cerr<<"OOOOOO"<<endl;
vector<int>st;
for (int i:message){
if (!used[i]){
used[i]=true;
ans+="10";
st.push_back(i);
} else {
while (st.back()!=i){
ans+="01";
st.pop_back();
}
ans+="11";
// st.push_back(i);
}
}
// if (ans.size()+Lg>100){
// while (true){
// ans+="0";
// }
// }
while (ans.size()<100) ans+="0";
for (int i=0;i<Lg;i++){
if (CNT&(1<<i)){
ans[100-i-1]='1';
}
}
} else {
for (int i=0;i<100;i++) ans+="0";
for (int i=0;i<Lg;i++){
if (CNT&(1<<i)) ans[i]='1';
}
}
return ans;
}
} else if (i+k+2==n){
string ans="";
for (int i=0;i<100;i++) ans+="0";
ans[0]=a[0][0][0];
ans[1]=a[1][0][0];
for (int i=2;i<100;i++) ans[i]=a[2][0][i-2];
ans[n]=a[0][1][0];
ans[n+1]=a[1][1][0];
for (int i=n+2;i<n*2;i++) ans[i]=a[2][1][i-n-2];
return ans;
} else if (j+k+2==n){
string ans="";
for (int i=0;i<100;i++) ans+="0";
ans[0]=a[0][0][0];
ans[1]=a[0][1][0];
for (int i=2;i<n;i++) ans[i]=a[0][2][i-2];
ans[n]=a[1][0][0];
ans[n+1]=a[1][1][0];
for (int i=n+2;i<n*2;i++) ans[i]=a[1][2][i-n-2];
return ans;
} else {
return a[0][0];
}
}
/**
1
2
1 1 0 1 1
1 1 0 0 0
1 0 1 1 1
0 1 0 0 0
0 1 1 1 1
1
3
1 0 1 1 1 0 0
0 0 1 0 1 0 0
1 1 1 0 1 0 0
1 0 0 0 1 0 0
0 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
4
**/
Compilation message (stderr)
mars.cpp: In function 'std::vector<int> decrypt(std::string, int, std::string)':
mars.cpp:10:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
10 | for (int i=0;i<100 && ans.size()<sz;i+=2){
| ~~~~~~~~~~^~~
mars.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0;i<t.size();i++){
| ~^~~~~~~~~
mars.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | while (j+1<t.size() && t[j+1]=='1') j++;
| ~~~^~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i=0;i<message.size();i++){
| ~^~~~~~~~~~~~~~~
mars.cpp:232:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
232 | for (int i=0;i<message.size();i++){
| ~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |