| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 602322 |
2022-07-22T21:57:16 Z |
duality |
Mars (APIO22_mars) |
C++17 |
|
8 ms |
1964 KB |
#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;
}
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),((l1-2)*(l2-2)+1)/2);
int m = *max_element(x00.first.begin(),x00.first.end());
for (auto &p: x01.first) {
if (p != -2) p += m;
}
m = *max_element(x01.first.begin(),x01.first.end());
for (auto &p: x10.first) {
if (p != -2) p += m;
}
m = *max_element(x10.first.begin(),x10.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 == 0) && (j == 1)) grid[i][j] = x00.first[1];
if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
if ((i == 1) && (j == 0)) 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 == l1-1) grid[i][j] = x11.first[j-2+(l1-3)];
else if (j == l2-1) grid[i][j] = x11.first[l1-i-1+(l1-3)+(l2-3)];
else if (i == 2) grid[i][j] = x11.first[l2-j-1+2*(l1-3)+(l2-3)];
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 = encode(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());
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 == 0) && (j == 1)) grid[i][j] = x00.first[1];
if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
if ((i == 1) && (j == 0)) 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());
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 == 0) && (j == 1)) grid[i][j] = x00.first[1];
if ((i == 1) && (j == 1)) grid[i][j] = x00.first[2];
if ((i == 1) && (j == 0)) 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 = encode(0);
//cout << ans << endl;
return ans;
}
}
}
Compilation message
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 process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:228:23: warning: statement has no effect [-Wunused-value]
228 | debug "here";
| ^~~~~~
mars.cpp:224:13: warning: unused variable 'si' [-Wunused-variable]
224 | int si = *upper_bound(vvv.begin(),vvv.end(),i)-i1;
| ^~
mars.cpp:225:13: warning: unused variable 'sj' [-Wunused-variable]
225 | int sj = *upper_bound(vvv.begin(),vvv.end(),j)-j1;
| ^~
mars.cpp:364:13: warning: unused variable 'mcom' [-Wunused-variable]
364 | int mcom = (d1*d2+1)/2;
| ^~~~
mars.cpp:199:9: warning: unused variable 'n2' [-Wunused-variable]
199 | int n2 = (n1+1)/2+!(((n1+1)/2) & 1);
| ^~
mars.cpp:200:9: warning: unused variable 'n3' [-Wunused-variable]
200 | int n3 = (s-n1)/2+(((s-n1)/2) & 1);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1936 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
