제출 #602336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602336		duality	화성 (APIO22_mars)	C++17	36 / 100	245 ms	3636 KiB

mars

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "mars.h"

string mult(string a,int x) {
    int i,c = 0;
    for (i = 0; i < a.size(); i++) {
        c += (a[i]-'0')*x;
        a[i] = (c % 2)+'0',c /= 2;
    }
    return a;
}
string add(string a,int x) {
    int i,c = x;
    for (i = 0; i < a.size(); i++) {
        c += a[i]-'0';
        a[i] = (c % 2)+'0',c /= 2;
    }
    return a;
}
int rem(string a,int x) {
    int i,c = 0;
    for (i = a.size()-1; i >= 0; i--) c = (c*2+(a[i]-'0')) % x;
    return c;
}
string div(string a,int x) {
    int i,c = 0;
    for (i = a.size()-1; i >= 0; i--) {
        c = c*2+(a[i]-'0');
        a[i] = (c / x)+'0',c %= x;
    }
    return a;
}
vector<vi> grid;
int doDFS(int x,int y,int c) {
    if ((x < 0) || (x >= grid.size()) || (y < 0) || (y >= grid[0].size())) return 0;
    else if (grid[x][y] != -1) return 0;
    grid[x][y] = c;
    doDFS(x-1,y,c),doDFS(x+1,y,c),doDFS(x,y-1,c),doDFS(x,y+1,c);
    return 0;
}
int merge(int a,int b) {
    if ((a == -2) || (b == -2)) return 0;
    int i,j;
    for (i = 0; i < grid.size(); i++) {
        for (j = 0; j < grid[i].size(); j++) {
            if (grid[i][j] == b) grid[i][j] = a;
        }
    }
    return 0;
}
int tcom = 0;
string encode(int com) {
    int i,j;
    int d1 = grid.size(),d2 = grid[0].size();
    int mcom = (d1*d2+1)/2;
    set<int> all,border;
    for (i = 0; i < d1; i++) {
        for (j = 0; j < d2; j++) all.insert(grid[i][j]);
    }
    for (i = 0; i < d2; i++) border.insert(grid[0][i]),border.insert(grid[d1-1][i]);
    for (i = 0; i < d1; i++) border.insert(grid[i][0]),border.insert(grid[i][d2-1]);
    all.erase(-2),border.erase(-2);
    vi order;
    for (i = 0; i < d1; i++) order.pb(grid[i][0]);
    for (i = 1; i < d2; i++) order.pb(grid[d1-1][i]);
    for (i = d1-2; i >= 0; i--) order.pb(grid[i][d2-1]);
    for (i = d2-2; i > 0; i--) order.pb(grid[0][i]);
    vi num,S,ops;
    int c = 0;
    for (i = 0; i < order.size(); i++) {
        if (order[i] == -2) num.pb(0);
        else {
            num.pb(1),c++;
            for (j = 0; j < S.size(); j++) {
                if (S[j] == order[i]) break;
            }
            if (j == S.size()) S.pb(order[i]),ops.pb(1);
            else {
                while (S.back() != order[i]) ops.pb(-1),S.pop_back();
                ops.pb(-1),ops.pb(1);
            }
        }
    }
    while (!S.empty()) ops.pb(-1),S.pop_back();
    assert(ops.size() == 2*c);
    c = 0;
    for (i = 0; i < num.size(); i++) {
        if (num[i] == 1) {
            if ((ops[c] == 1) && (ops[c+1] == 1)) num[i] = 1;
            else if ((ops[c] == 1) && (ops[c+1] == -1)) num[i] = 2;
            else if ((ops[c] == -1) && (ops[c+1] == 1)) num[i] = 3;
            else if ((ops[c] == -1) && (ops[c+1] == -1)) num[i] = 4;
            else assert(0);
            c += 2;
        }
    }
    printArr(num,num.size());
    string big = string(100,'0');
    for (i = (int) num.size()-1; i >= 0; i--) big = add(mult(big,5),num[i]);
    big = add(mult(big,mcom),all.size()-border.size()+com);
    tcom = com+all.size();
    return big;
}
string encode2(int com) {
    int i,j;
    int d1 = grid.size(),d2 = grid[0].size();
    int mcom = (d1*d2+1)/2;
    set<int> all,border;
    for (i = 0; i < d1; i++) {
        for (j = 0; j < d2; j++) all.insert(grid[i][j]);
    }
    for (i = 0; i < d2; i++) border.insert(grid[0][i]);
    for (i = 0; i < d1; i++) border.insert(grid[i][0]);
    all.erase(-2),border.erase(-2);
    vi order;
    for (i = 0; i < d1; i++) order.pb(grid[i][0]);
    for (i = d2-1; i > 0; i--) order.pb(grid[0][i]);
    vi num,S,ops;
    int c = 0;
    for (i = 0; i < order.size(); i++) {
        if (order[i] == -2) num.pb(0);
        else {
            num.pb(1),c++;
            for (j = 0; j < S.size(); j++) {
                if (S[j] == order[i]) break;
            }
            if (j == S.size()) S.pb(order[i]),ops.pb(1);
            else {
                while (S.back() != order[i]) ops.pb(-1),S.pop_back();
                ops.pb(-1),ops.pb(1);
            }
        }
    }
    while (!S.empty()) ops.pb(-1),S.pop_back();
    assert(ops.size() == 2*c);
    c = 0;
    for (i = 0; i < num.size(); i++) {
        if (num[i] == 1) {
            if ((ops[c] == 1) && (ops[c+1] == 1)) num[i] = 1;
            else if ((ops[c] == 1) && (ops[c+1] == -1)) num[i] = 2;
            else if ((ops[c] == -1) && (ops[c+1] == 1)) num[i] = 3;
            else if ((ops[c] == -1) && (ops[c+1] == -1)) num[i] = 4;
            else assert(0);
            c += 2;
        }
    }
    printArr(num,num.size());
    string big = string(100,'0');
    for (i = (int) num.size()-1; i >= 0; i--) big = add(mult(big,5),num[i]);
    big = add(mult(big,mcom),all.size()-border.size()+com);
    tcom = com+all.size();
    return big;
}
pair<vi,int> decode(string a,int border,int mcom) {
    //cout<<a<<" "<<border<<" "<<mcom<<endl;
    int i;
    int com = rem(a,mcom);
    a = div(a,mcom);
    vi vv;
    int c = 0;
    vi ops;
    for (i = 0; i < border; i++) {
        vv.pb(rem(a,5)),a = div(a,5),c += vv.back() > 0;
        if (vv.back() == 1) ops.pb(1),ops.pb(1);
        if (vv.back() == 2) ops.pb(1),ops.pb(-1);
        if (vv.back() == 3) ops.pb(-1),ops.pb(1);
        if (vv.back() == 4) ops.pb(-1),ops.pb(-1);
    }
    printArr(vv,vv.size());
    printArr(ops,ops.size());
    int t = 1;
    vi v(border,-2);
    vi S;
    c = 0;
    for (i = 0; i < border; i++) {
        if (vv[i] > 0) {
            int l = t++;
            while (ops[c] == -1) l = S.back(),S.pop_back(),c++;
            v[i] = l,S.pb(l),c++;
        }
    }
    printArr(v,v.size());
    printVar(com);
    return mp(v,com);
}
int findBorder(int w,int h) {
    assert((w >= 2) && (h >= 2));
    return 2*w+2*h-4;
}
string process(vector<vector<string> > a,int i,int j,int k,int n) {
    if ((i & 1) || (j & 1)) return a[0][0];
    int s = 2*n+1;
    int n1 = n+!(n & 1);
    int n2 = (n1+1)/2+!(((n1+1)/2) & 1);
    int n3 = (s-n1)/2+(((s-n1)/2) & 1);
    k = n-1-k;
    /*if (k == 0) {
        a[0][0],a[0][2],a[2][0],a[2][2];
    }
    else if (k < (s-n1)/2) return a[2*(i > 0)][2*(j > 0)];
    else if (k == n1/2) {
        if (((i == 0) || (i == s-n1)) && ((j == 0) || (j == s-n1))) {
            a[0][0],a[0][2],a[2][0],a[2][2];
        }
        else return a[0][0];
    }
    else if (k < ???) {
        return a[2*(i > 0)][2*(j > 0)];
    }
    else if (k < n-1) {*/
    if (k < n-1) {
        int p = n-1-k;
        //vi vvv = {s-n1-n3,s-n1,s-n2,s};
        vi vvv = {s};
        int l1 = *upper_bound(vvv.begin(),vvv.end(),i)-i;
        int l2 = *upper_bound(vvv.begin(),vvv.end(),j)-j;
        int i1 = *(--upper_bound(vvv.begin(),vvv.end(),i));
        int j1 = *(--upper_bound(vvv.begin(),vvv.end(),j));
        int si = *upper_bound(vvv.begin(),vvv.end(),i)-i1;
        int sj = *upper_bound(vvv.begin(),vvv.end(),j)-j1;
        if (i-j == i1-j1) {
            if (p+1 == max(l1/2,l2/2)) {
                debug "here";
                printVar(l1);
                printVar(l2);
                // merge 4
                auto x00 = decode(a[0][0],4,2);
                auto x01 = decode(a[0][2],2*(l2-2),l2-2);
                auto x10 = decode(a[2][0],2*(l1-2),l1-2);
                auto x11 = decode(a[2][2],findBorder(l1-2,l2-2)/2+1,((l1-2)*(l2-2)+1)/2);
                int m = *max_element(x00.first.begin(),x00.first.end());
                m = max(m,1);
                for (auto &p: x01.first) {
                    if (p != -2) p += m;
                }
                m = *max_element(x01.first.begin(),x01.first.end());
                m = max(m,1);
                m = max(m,*max_element(x00.first.begin(),x00.first.end()));
                for (auto &p: x10.first) {
                    if (p != -2) p += m;
                }
                m = *max_element(x10.first.begin(),x10.first.end());
                m = max(m,1);
                m = max(m,*max_element(x00.first.begin(),x00.first.end()));
                m = max(m,*max_element(x01.first.begin(),x01.first.end()));
                for (auto &p: x11.first) {
                    if (p != -2) p += m;
                }
                printArr(x00.first,x00.first.size());
                printArr(x01.first,x01.first.size());
                printArr(x10.first,x10.first.size());
                printArr(x11.first,x11.first.size());
                grid.clear();
                grid.resize(l1);
                for (i = 0; i < l1; i++) {
                    grid[i].resize(l2);
                    for (j = 0; j < l2; j++) {
                        if ((i < 2) && (j < 2)) {
                            if ((i == 0) && (j == 0)) grid[i][j] = x00.first[0];
                            if ((i == 1) && (j == 0)) grid[i][j] = x00.first[1];
                            if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
                            if ((i == 0) && (j == 1)) grid[i][j] = x00.first[3];
                        }
                        else if (i < 2) {
                            if ((i == 0) && (j == 2)) grid[i][j] = x01.first[0];
                            else if (i == 1) grid[i][j] = x01.first[j-1];
                            else grid[i][j] = x01.first[2*l2-j-2];
                        }
                        else if (j < 2) {
                            if (j == 0) grid[i][j] = x10.first[i-2];
                            else grid[i][j] = x10.first[2*l1-i-3];
                        }
                        else {
                            if (j == 2) grid[i][j] = x11.first[i-2];
                            else if (i == 2) grid[i][j] = x11.first[l2-j-1+l1-2];
                            else grid[i][j] = -2;
                        }
                    }
                }
                print2dArr(grid,l1,l2);
                for (i = 0; i < l1; i++) merge(grid[i][1],grid[i][2]);
                for (i = 0; i < l2; i++) merge(grid[1][i],grid[2][i]);
                print2dArr(grid,l1,l2);
                string ans = encode2(x00.second+x01.second+x10.second+x11.second);
                if (k == 0) {
                    string ans(100,'0');
                    for (i = 0; i < 20; i++) {
                        if (tcom & (1 << i)) ans[i] = '1';
                    }
                    return ans;
                }
                else return ans;
            }
            else return a[0][0];
        }
        else if (i-j > i1-j1) {
            if (p+1 == l1/2) {
                // merge down
                auto x00 = decode(a[0][0],4,2),x10 = decode(a[2][0],2*(l1-2),l1-2);
                int m = *max_element(x00.first.begin(),x00.first.end());
                m = max(m,1);
                for (auto &p: x10.first) {
                    if (p != -2) p += m;
                }
                grid.clear();
                grid.resize(l1);
                for (i = 0; i < l1; i++) {
                    grid[i].resize(2);
                    for (j = 0; j < 2; j++) {
                        if ((i < 2) && (j < 2)) {
                            if ((i == 0) && (j == 0)) grid[i][j] = x00.first[0];
                            if ((i == 1) && (j == 0)) grid[i][j] = x00.first[1];
                            if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
                            if ((i == 0) && (j == 1)) grid[i][j] = x00.first[3];
                        }
                        else if (j < 2) {
                            if (j == 0) grid[i][j] = x10.first[i-2];
                            else grid[i][j] = x10.first[2*l1-i-3];
                        }
                    }
                }
                for (i = 0; i < 2; i++) merge(grid[1][i],grid[2][i]);
                string ans = encode(x00.second+x10.second);
                return ans;
            }
            else return a[0][0];
        }
        else {
            if (p+1 == l2/2) {
                // merge right
                auto x00 = decode(a[0][0],4,2),x01 = decode(a[0][2],2*(l2-2),l2-2);
                int m = *max_element(x00.first.begin(),x00.first.end());
                m = max(m,1);
                for (auto &p: x01.first) {
                    if (p != -2) p += m;
                }
                grid.clear();
                grid.resize(2);
                for (i = 0; i < 2; i++) {
                    grid[i].resize(l2);
                    for (j = 0; j < l2; j++) {
                        if ((i < 2) && (j < 2)) {
                            if ((i == 0) && (j == 0)) grid[i][j] = x00.first[0];
                            if ((i == 1) && (j == 0)) grid[i][j] = x00.first[1];
                            if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
                            if ((i == 0) && (j == 1)) grid[i][j] = x00.first[3];
                        }
                        else if (i < 2) {
                            if ((i == 0) && (j == 2)) grid[i][j] = x01.first[0];
                            else if (i == 1) grid[i][j] = x01.first[j-1];
                            else grid[i][j] = x01.first[2*l2-j-2];
                        }
                    }
                }
                for (i = 0; i < 2; i++) merge(grid[i][1],grid[i][2]);
                string ans = encode(x00.second+x01.second);
                return ans;
            }
            else return a[0][0];
        }
    }
    else {
        int d1 = (i < s-3) ? 2:3;
        int d2 = (j < s-3) ? 2:3;
        int mcom = (d1*d2+1)/2;
        int i,j;
        grid.clear();
        for (i = 0; i < d1; i++) {
            grid.pb(vi());
            for (j = 0; j < d2; j++) grid.back().pb((a[i][j][0] == '1') ? -1:-2);
        }
        print2dArr(grid,d1,d2);
        int com = 0;
        for (i = 0; i < d1; i++) {
            for (j = 0; j < d2; j++) {
                if (grid[i][j] == -1) doDFS(i,j,com),com++;
            }
        }
        if (n == 1) {
            string ans(100,'0');
            for (i = 0; i < 20; i++) {
                if (com & (1 << i)) ans[i] = '1';
            }
            return ans;
        }
        else {
            string ans = ((d1 == 3) && (d2 == 3)) ? encode2(0):encode(0);
            //cout << ans << endl;
            return ans;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

mars.cpp: In function 'std::string mult(std::string, int)':
mars.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~
mars.cpp: In function 'std::string add(std::string, int)':
mars.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~
mars.cpp: In function 'int doDFS(int, int, int)':
mars.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     if ((x < 0) || (x >= grid.size()) || (y < 0) || (y >= grid[0].size())) return 0;
      |                     ~~^~~~~~~~~~~~~~
mars.cpp:90:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     if ((x < 0) || (x >= grid.size()) || (y < 0) || (y >= grid[0].size())) return 0;
      |                                                      ~~^~~~~~~~~~~~~~~~~
mars.cpp: In function 'int merge(int, int)':
mars.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (i = 0; i < grid.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
mars.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (j = 0; j < grid[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~
mars.cpp: In function 'std::string encode(int)':
mars.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (i = 0; i < order.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
mars.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |             for (j = 0; j < S.size(); j++) {
      |                         ~~^~~~~~~~~~
mars.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             if (j == S.size()) S.pb(order[i]),ops.pb(1);
      |                 ~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from mars.cpp:3:
mars.cpp:140:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |     assert(ops.size() == 2*c);
      |            ~~~~~~~~~~~^~~~~~
mars.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (i = 0; i < num.size(); i++) {
      |                 ~~^~~~~~~~~~~~
mars.cpp: In function 'std::string encode2(int)':
mars.cpp:175:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for (i = 0; i < order.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
mars.cpp:179:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             for (j = 0; j < S.size(); j++) {
      |                         ~~^~~~~~~~~~
mars.cpp:182:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |             if (j == S.size()) S.pb(order[i]),ops.pb(1);
      |                 ~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from mars.cpp:3:
mars.cpp:190:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  190 |     assert(ops.size() == 2*c);
      |            ~~~~~~~~~~~^~~~~~
mars.cpp:192:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for (i = 0; i < num.size(); i++) {
      |                 ~~^~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:278:23: warning: statement has no effect [-Wunused-value]
  278 |                 debug "here";
      |                       ^~~~~~
mars.cpp:274:13: warning: unused variable 'si' [-Wunused-variable]
  274 |         int si = *upper_bound(vvv.begin(),vvv.end(),i)-i1;
      |             ^~
mars.cpp:275:13: warning: unused variable 'sj' [-Wunused-variable]
  275 |         int sj = *upper_bound(vvv.begin(),vvv.end(),j)-j1;
      |             ^~
mars.cpp:420:13: warning: unused variable 'mcom' [-Wunused-variable]
  420 |         int mcom = (d1*d2+1)/2;
      |             ^~~~
mars.cpp:249:9: warning: unused variable 'n2' [-Wunused-variable]
  249 |     int n2 = (n1+1)/2+!(((n1+1)/2) & 1);
      |         ^~
mars.cpp:250:9: warning: unused variable 'n3' [-Wunused-variable]
  250 |     int n3 = (s-n1)/2+(((s-n1)/2) & 1);
      |         ^~

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