제출 #572601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572601		oleh1421	화성 (APIO22_mars)	C++17	100 / 100	1335 ms	4892 KiB

mars

#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


**/

컴파일 시 표준 에러 (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++){
      |                          ~^~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11