제출 #602336

#제출 시각아이디문제언어결과실행 시간메모리
602336duality화성 (APIO22_mars)C++17
36 / 100
245 ms3636 KiB
#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);
      |         ^~
#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...