Submission #572601

#TimeUsernameProblemLanguageResultExecution timeMemory
572601oleh1421Mars (APIO22_mars)C++17
100 / 100
1335 ms4892 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...