| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 335215 |
2020-12-11T14:25:21 Z |
guka415 |
ČVENK (COI15_cvenk) |
C++14 |
|
202 ms |
13036 KB |
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll; //OVERFLOW
inline int dist(int x, int y, int lx, int ly) {
return abs(x - lx) + abs(y - ly);
}
inline pii upperLeft(int x, int y, int bit) {
int len = (1 << bit);
return { (x / len)*len,(y / len)*len };
}
inline int whichTriangle(int x, int y, int bit) {
pii ul = upperLeft(x, y, bit);
int len2 = (1 << (bit - 1));
if (x - ul.first < len2&&y - ul.second < len2)return 0;
else if (x - ul.first >= len2)return 1;
else return 2;
}
inline int tz(int x, int y, int bit) {
if (whichTriangle(x, y, bit) == 0)return 0;
pii ttt = upperLeft(x, y, bit-1);
return dist(ttt.first, ttt.second, x, y) + 1;
}
inline int to(int x, int y, int bit) {
pii ttt = upperLeft(x, y, bit);
int tx = (1 << (bit - 1)), ty = 0;
switch (whichTriangle(x, y, bit)) {
case 1:
return 0;
case 2:
return dist(ttt.first, ttt.second, x, y) + (1 << (bit - 1));
case 0:
int mx = x - ttt.first, my = y - ttt.second, crb = bit;
ll bst = 1e18;
while (crb > 0) {
pii tmp = upperLeft(mx, my, crb);
if (tmp.first&&tmp.second)return bst;
bst = min(bst, (ll)dist(tmp.first, tmp.second, mx, my) + dist(tmp.first, tmp.second, tx, ty));
crb--;
}
return bst;
}
return -1;
}
inline int tt(int x, int y, int bit) {
pii ttt = upperLeft(x, y, bit);
int ty = (1 << (bit - 1)), tx = 0;
switch (whichTriangle(x, y, bit)) {
case 2:
return 0;
case 1:
return dist(ttt.first, ttt.second, x, y) + (1 << (bit - 1));
case 0:
int mx = x - ttt.first, my = y - ttt.second, crb = bit;
ll bst = 1e18;
while (crb > 0) {
pii tmp = upperLeft(mx, my, crb);
if (tmp.first&&tmp.second)return bst;
bst = min(bst, (ll)dist(tmp.first, tmp.second, mx, my) + dist(tmp.first, tmp.second, tx, ty));
crb--;
}
return bst;
}
return -1;
}
int main() {
fast;
int n;
map<pii, ll> mem;
cin >> n;
foru(i, 0, n) {
int ax, bx;
cin >> ax >> bx;
mem[{ax, bx}]++;
}
int cbt = 30;
ll tot = 0;
while (cbt > 0) {
ll crtot[3]{ 0,0,0 };
map<pii, ll> cnts;
bool f = 1;
pii ul;
for (auto x : mem) {
if (f) {
ul = upperLeft(x.first.first, x.first.second, cbt);
f = 0;
}
crtot[0] += x.second*tz(x.first.first, x.first.second, cbt);
crtot[1] += x.second*to(x.first.first, x.first.second, cbt);
crtot[2] += x.second*tt(x.first.first, x.first.second, cbt);
}
int mni = -1;
ll mymn = 1e18;
foru(i, 0, 3) {
if (crtot[i] < mymn) {
mymn = crtot[i];
mni = i;
}
}
pll out1 = { ul.first + (1 << (cbt - 1)),ul.second };
pll out2 = { ul.first,ul.second + (1 << (cbt - 1)) };
switch (mni) {
case 0:
for (auto x : mem) {
switch (whichTriangle(x.first.first, x.first.second, cbt)) {
case 0:
cnts[x.first] += x.second;
break;
case 1:
cnts[{out1.first - 1, out1.second}] += x.second;
break;
case 2:
cnts[{out2.first, out2.second - 1}] += x.second;
break;
}
}
break;
case 1:
for (auto x : mem) {
if (whichTriangle(x.first.first, x.first.second, cbt) != 1) cnts[out1] += x.second;
else cnts[x.first] += x.second;
}
break;
case 2:
for (auto x : mem) {
if (whichTriangle(x.first.first, x.first.second, cbt) != 2) cnts[out2] += x.second;
else cnts[x.first] += x.second;
}
break;
}
mem = cnts;
tot += mymn;
cbt--;
}
cout << tot << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
1260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
13036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
