| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846480 |
2023-09-07T15:43:09 Z |
vjudge1 |
ČVENK (COI15_cvenk) |
C++17 |
|
3000 ms |
329324 KB |
// Imagine not FFT
#include <bits/stdc++.h>
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define DEBUG(x) std::cerr << #x << ": " << x << std::endl;
#define DEBUGP(x) std::cerr << #x << ": { " << x.ff << " , " << x.ss << " }" << std::endl;
#define DEBUGV(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << ___y << " "; std::cerr << "}" << std::endl;
#define DEBUGVV(x) std::cerr << #x << ": { \n"; for(int _i=0;_i<sz(x);++_i) {DEBUGV(x[_i]);} std::cerr << "}" << std::endl;
#define DEBUGVP(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << "{" << ___y.first << "," << ___y.second << "}" << " "; std::cerr << "}" << std::endl;
#define DEBUGPII(x) std::cerr << #x << ": { " << x.first << " , " << x.second << " }" << endl;
#define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
#else
#define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
#define DEBUG(...) void(23);
#define DEBUGP(...) void(23);
#define DEBUGV(x) void(23);
#define DEBUGARR(arr, size) void(23);
#define DEBUGPRINT(...) void(23);
#define DEBUGMAP(...) void(23);
#define DEBUGMAPQUEUE(...) void(23);
#define DEBUGVV(x) void(23);
#define DEBUGVP(x) void(23);
#define DEBUGPII(x) void(23);
#define files void(23);
#endif
#define int long long
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pii std::pair < int , int >
#define pll std::pair < ll , ll >
#define vi std::vector < int >
#define vl std::vector < ll >
#define vii std::vector < pii >
#define vll std::vector < pll >
#define vvi std::vector < vi >
#define vvii std::vector < vii >
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define forn(i,j) for(int i=0;i<j;i++)
#define forr(i,j,k) for(int i=j;i<k;i++)
#define mset multiset
#define pqueue priority_queue
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
#define sz(a) (int)(a.size())
using namespace std;
map < pii , int > calc;
inline int minBit(int a){
if(a==0) return 0;
return (a&-a);
}
bool isSame(pii a, pii b){
if(a.ff == 0 && b.ff == 0) return true;
if(a.ss == 0 && b.ss == 0) return true;
if(a.ff == 0){
while(minBit(b.ff)>0 && minBit(b.ff)<minBit(b.ss)) {b.ff-=minBit(b.ff);}
return (a==b);
return ((a==b)||(a.ff==0) || (b.ff==0));
}
if(a.ss == 0){
while(minBit(b.ss)>0 && minBit(b.ss)<minBit(b.ss)) {b.ss-=minBit(b.ss);}
return (a==b);
return ((a==b)||(a.ss==0) || (b.ss==0));
}
if(b.ff == 0){
while(minBit(a.ff)>0 && minBit(a.ff)<minBit(a.ss)) {a.ff-=minBit(a.ff);if(a==b) return true;}
return (a==b);
return ((a==b)||(a.ff==0) || (b.ff==0));
}
if(b.ss == 0){
while(minBit(a.ss)>0 && minBit(a.ss)<minBit(a.ss)) {a.ss-=minBit(a.ss);if(a==b) return true;}
return (a==b);
return ((a==b)||(a.ss==0) || (b.ss==0));
}
if(minBit(a.ff)<minBit(a.ss)){
if(minBit(b.ff)>minBit(b.ss)) return false;
while(minBit(a.ff)>0 && minBit(a.ff)<minBit(a.ss)) {a.ff-=minBit(a.ff);if(a==b) return true;}
while(minBit(b.ff)>0 && minBit(b.ff)<minBit(b.ss)) {b.ff-=minBit(b.ff);if(a==b) return true;}
return (a==b);
return ((a==b)||(a.ff==0) || (b.ff==0));
}
else {
if(minBit(b.ff)<minBit(b.ss)) return false;
while(minBit(a.ss)>0 && minBit(a.ff)>minBit(a.ss)) {a.ss-=minBit(a.ss);if(a==b) return true;}
while(minBit(b.ss)>0 && minBit(b.ff)>minBit(b.ss)) {b.ss-=minBit(b.ss);if(a==b) return true;}
return (a==b);
return ((a==b)||(a.ss==0) || (b.ss==0));
}
}
int totCount(int a, int b){
int ret = (a>0)+(b>0);
int x = (minBit(a)<minBit(b) ? 0:1);
(minBit(a)<minBit(b) ? a-=minBit(a):b-=minBit(b));
while(a>0 || b>0){
if(b==0 || (a>0 && minBit(a)<minBit(b))){if(x==1) ++ret;x=0;a-=minBit(a);}
else if(a==0 || (b>0 && minBit(b))){if(x==0) ++ret;x=1;b-=minBit(b);}
}
return ret;
}
int dec(int& a, int& b){
if(a==0 && b==0) return 0;
int ans = 0;
if(a>0 && minBit(a)<minBit(b))
while(a > 0 && minBit(a)<minBit(b)) {ans+=minBit(a);a-=minBit(a);}
else if(b>0 && minBit(b)<minBit(a))
while(b>0 && minBit(b)<minBit(a)) {ans+=minBit(b);b-=minBit(b);}
return ans;
}
int calcTot(vii&a,int x, int y){
swap(x,y);
if(calc[{x,y}]!=0) return calc[{x,y}];
if((x&y)>1 || x<0 || y<0) return 100000000000000000ll;
int totCountpo = totCount(x,y);
int ans = 0;
for(auto p:a){
if(p.ff==x && p.ss==y) continue;
int totCountxy=totCountpo;
int totCountp=totCount(p.ff,p.ss);
int tx=x,ty=y;
while(totCountxy>totCountp) {ans+=dec(tx,ty);--totCountxy;}
while(totCountxy<totCountp) {ans+=dec(p.ff,p.ss);--totCountp;}
if(isSame(p,{tx,ty})) {
ans+=abs(p.ff-tx) + abs(p.ss-ty);
continue;
}
forn(i,32){
if(p.ff==tx&&p.ss==ty) break;
int b = (1<<i);
if(((tx|ty)&b)) ans+=b;
if(((p.ff|p.ss)&b)) ans+=b;
if((tx&b)) tx-=(b);
else if((ty&b)) ty-=(b);
if((p.ff&b)) p.ff-=(b);
else if((p.ss&b)) p.ss-=(b);
if(isSame(p,{tx,ty})) break;
}
ans+=abs(p.ff-tx) + abs(p.ss-ty);
}
calc[{x,y}]=ans;
return ans;
}
int getHowfarD(int a, int b){
swap(a,b);
if(a==0) return (int)(1ll<<3);
return (a&-a)-(b)%(a&-a)-1;
}
int getHowfarR(int a, int b){
if(a==0) return (int)(1ll<<3);
return (a&-a)-(b)%(a&-a)-1;
}
int bsDown(vii& a, int l, int r,int o/*ther*/){
int m = (r+l)/2;
while(l<r){
int mans = calcTot(a,m,o);
if(calcTot(a,r,o)<=mans) l=m;
else if(calcTot(a,l,o)<=mans) r=m;
else {l=(m+l)/2+1;r=(m+r)/2;}
m = (r+l)/2;
if(l+1==r && calcTot(a,r,o)<calcTot(a,l,o)) return l;
if(l+1==r && calcTot(a,r,o)>calcTot(a,l,o)) return l;
}
return l;
}
int bsRight(vii& a, int l, int r,int o/*ther*/){
int m = (r+l)/2;
int oldM = -1;
while(l<r){
int mans = calcTot(a,o,m);
if(calcTot(a,o,r)<=mans) l=m;
else if(calcTot(a,o,l)<=mans) r=m;
else {l=(m+l)/2+1;r=(m+r)/2;}
m = (r+l)/2;
DEBUG(l)
DEBUG(m)
DEBUG(r)
DEBUG(o)
if(l+1==r && calcTot(a,o,r)<calcTot(a,o,l)) return l;
else if(l+1==r) return l;
}
return l;
}
int getAns(vii& a){
int posX = 0;
int posY = 0;
int i=0,j=0;
pair < int , int > oldPos={-1,-1};
int ans = calcTot(a,0,0);
while(oldPos.ss!=posX || oldPos.ff != posY){
oldPos = make_pair(posY,posX);
int down=bsDown(a,posY,posY+getHowfarD(posY,posX),posX);
if(((down+i)&(posX+j))==0 && ans>calcTot(a,down+i,posX+j)){
posY=down+i;
ans=calcTot(a,posY+j,posX+i);
}
int right=bsRight(a,posX,posX+getHowfarR(posY,posX),posY);
if(((posY+i)&(right+j))==0 && ans>calcTot(a,posY+i,right+j)){
posX=right+j;
ans=calcTot(a,posY+j,posX+i);
}
}
cerr << oldPos.ss << " " << oldPos.ff << endl;
return ans;
}
void solve(int _t_case){
//srand(time(0));
int n;
cin >> n;
vii a(n);
for(auto&x:a) cin >> x.ff >> x.ss;
int ans = getAns(a);
cout << ans << endl;
cerr << calcTot(a,0,3) << endl;
cerr << calcTot(a,0,4) << endl;
return;
}
signed main(){
//bs(1,4);
fastio;
files;
int t=1,_t=0;
while(_t<t){
++_t;
solve(_t);
}
return 0;
}
Compilation message
cvenk.cpp: In function 'long long int bsRight(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
cvenk.cpp:186:6: warning: unused variable 'oldM' [-Wunused-variable]
186 | int oldM = -1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3117 ms |
329324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3092 ms |
9736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
2008 KB |
Output is correct |
| 2 |
Correct |
99 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
161 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
85 ms |
2004 KB |
Output is correct |
| 5 |
Correct |
45 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3075 ms |
2016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
