Submission #846424

#	Time	Username	Problem	Language	Result	Execution time	Memory
846424		vjudge1	ČVENK (COI15_cvenk)	C++17	0 / 100	3096 ms	71320 KiB

cvenk

// Imagine not FFT
#include <bits/stdc++.h>
//#define ONLINE_JUDGE
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
#define DEBUGVOID(x) void(23);
#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())
     
const int MOD = 1000000007;
const int MOD2 = 998244353;

using namespace std;


int add(int a, int b){
	return (a+b)%MOD2;
}

int addd(int& a, int b){
	return (a=((a+b)%MOD2));
}

int mul(int a, int b){
	return (a*b)%MOD2;
}

int mull(int& a, int b){
	return (a=((a*b)%MOD2));
}

int fpow(int a, int b){
	if(b==0) return 1;
	if(b==1) return a;
	int n=fpow(a,b/2);
	if(b%2==0) return mul(n,n);
	else return mul(mul(n,n),a);
//	return mul(mul(n,n),(b%2==1 ? a:1));
}

int div1(int a, int b){
	return (a*fpow(b,MOD2-2))%MOD2;
}

int divv(int& a, int b){
	return (a=((a*fpow(b,MOD2-2))%MOD2));
}

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);DEBUGVOID(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);DEBUGVOID(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);DEBUGVOID(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);DEBUGVOID(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);DEBUGVOID(a.ff);if(a==b) return true;}
		while(minBit(b.ff)>0 && minBit(b.ff)<minBit(b.ss)) {b.ff-=minBit(b.ff);DEBUGVOID(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);}
		DEBUGVOID(a);
		DEBUGVOID(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);DEBUGVOID(a);}
	else if(b>0 && minBit(b)<minBit(a))
		while(b>0 && minBit(b)<minBit(a)) {ans+=minBit(b);b-=minBit(b);DEBUGVOID(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;
	DEBUGVOID(x);
	int totCountpo = totCount(x,y);
	DEBUGVOID(x);
 	int ans = 0;
	for(auto p:a){
		if(p.ff==x && p.ss==y) continue;
		pii t_p = p;int t_ans = ans;
		int totCountxy=totCountpo;
		int totCountp=totCount(p.ff,p.ss);
		int tx=x,ty=y;
		DEBUGVOID(p.ff);
		while(totCountxy>totCountp) {ans+=dec(tx,ty);--totCountxy;DEBUGVOID(tx);DEBUGVOID(ty);}
		while(totCountxy<totCountp) {ans+=dec(p.ff,p.ss);--totCountp;DEBUGVOID(p);}
		DEBUGVOID(p.ff);
		if(isSame(p,{tx,ty})) {
			ans+=abs(p.ff-tx) + abs(p.ss-ty);
		//	cerr << "Dist from(" << t_p.ff << "," << t_p.ss << ") to (" << x << "," << y << ") is = " << ans-t_ans << endl;
			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);
			DEBUGVOID(i);
			if(isSame(p,{tx,ty})) break;
			//vector<int> EVERYTHING={p.ff,p.ss,tx,ty}; DEBUGV(EVERYTHING);
			DEBUGVOID((pair<int,int>{tx,ty}));
		}
		DEBUGVOID(abs(p.ff-tx) + abs(p.ss-ty));
		ans+=abs(p.ff-tx) + abs(p.ss-ty);

	//	cerr << "Dist from(" << t_p.ff << "," << t_p.ss << ") to (" << x << "," << y << ") is = " << ans-t_ans << endl;
	}
	calc[{x,y}]=ans;
	return ans;
}

int getHowfarD(int a, int b){
	swap(a,b);
	if(a==0) return 20;
	if(a==0) return (int)(1e9+1);
	return (a&-a)-(b)%(a&-a)-1;
}

int getHowfarR(int a, int b){
	if(a==0) return (int)(1e9+1);
	return (a&-a)-(b)%(a&-a)-1;
}

int bsDown(vii& a, int l, int r,int o/*ther*/){
	int m = (r+l)/2;
//	int lans = calcTot(a,l,o);
//	int rans = calcTot(a,r,o);
//	int oldM = -1;
	DEBUG(l);
	DEBUG(r);
	DEBUG(o);
	DEBUG(m);
	while(l<r){
		DEBUG(m);
		int mans0 = calcTot(a,m-1,o);
		int mans1 = calcTot(a,m,o);
		int mans2 = calcTot(a,m+1,o);
	//	cerr << "calcTot(a," << o << "," << m << ");" <<endl;
	//	cerr<<"D ";DEBUGV((vector<int>{l,m,r}));
	//	cerr<<"D ";DEBUGVP((vector<pii>{{m-1,o},{m,o},{m+1,o}}));
		DEBUG(mans0)
		DEBUG(mans1)
		DEBUG(mans2)
		DEBUG((mans2<mans1))
		DEBUG((mans0<mans1))
		if(mans2<mans1) l=m+1;
		else if(mans0<mans1) r=m-1;
		else {
			if(mans0==mans1 && getHowfarR(m-1,o)>getHowfarR(m,o)) return m-1;
			if(mans2==mans1 && getHowfarR(m+1,o)>getHowfarR(m,o)) return m+1;
			return m;
		}
		m = (r+l)/2;
	}
	return l;
}

int bsRight(vii& a, int l, int r,int o/*ther*/){
	int m = (r+l)/2;
//	int lans = calcTot(a,o,l);
//	int rans = calcTot(a,o,r);
//	int oldM = -1;
	DEBUG(l);
	DEBUG(r);
	DEBUG(o);
	DEBUG(m);
	while(l<r){
		int mans0 = calcTot(a,o,m-1);
		int mans1 = calcTot(a,o,m);
		int mans2 = calcTot(a,o,m+1);
		if(mans2<mans1) l=m+1;
		else if(mans0<mans1) r=m-1;
		else {
			if(mans0==mans1 && getHowfarD(o,m-1)>getHowfarD(o,m)) return m-1;
			if(mans2==mans1 && getHowfarD(o,m+1)>getHowfarD(o,m)) return m+1;
			return m;
		}
		m = (r+l)/2;
	//	cerr << "R ";DEBUGV((vector<int>{l,m,r}));
	}
	return l;
}

int getAns(vii& a){
	int posX = 0;
	int posY = 0;
	pair < int , int > oldPos={-1,-1};
	int ans = 100000000000000000ll;
	while(oldPos.ss!=posX || oldPos.ff != posY){
		oldPos = make_pair(posY,posX);
		//DEBUGV((vi{posY,posY+getHowfar(posX,posY),posX}));
		int down=bsDown(a,posY,posY+getHowfarD(posY,posX),posX);
		int right=bsRight(a,posX,posX+getHowfarR(posY,posX),posY);
		for(int i=0;i<=0;i++){
			for(int j=0;j<=0;j++){
				if(((down+i)&(posX+j))==0 && ans>calcTot(a,down+i,posX+j)){
					posY=down+i;
					ans=calcTot(a,posY+j,posX+i);
				}
				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.ff << "," << oldPos.ss << "} to {" << posX << "," << posY << "}" << endl;
	}
	DEBUGP(oldPos);
	return ans;
	//return oldPos;
}

void solve(int _t_case){
	DEBUG(isSame({8,4},{8,7}));
	DEBUG(isSame({8,4},{9,6}));
	DEBUG(isSame({8,4},{10,5}));
	DEBUG(isSame({8,4},{11,4}));
	int n;
	cin >> n;
	vii a(n);
	for(auto&x:a) cin >> x.ff >> x.ss;
	//DEBUG(calcTot(a,6,0));
	//DEBUG(calcTot(a,8,4));
	//DEBUG(calcTot(a,a[0].ff,a[0].ss));
	int ans = getAns(a);
	cout << ans << endl;
	DEBUG(calcTot(a,4,8));
	DEBUG(calcTot(a,5,8));
	DEBUG(calcTot(a,6,8));
	//cout << ans.ff << " " << ans.ss << endl;
	return;
}

signed main(){
 	fastio;
    files;
    int t=1,_t=0;
    //std::cin >> t;
    while(_t<t){
        ++_t;
        solve(_t);
    }
   // DEBUG(getHowfar(18,8))
 //   DEBUG(getHowfar(8,18))
    return 0;
}

Compilation message (stderr)

cvenk.cpp: In function 'long long int calcTot(std::vector<std::pair<long long int, long long int> >&, long long int, long long int)':
cvenk.cpp:181:7: warning: variable 't_p' set but not used [-Wunused-but-set-variable]
  181 |   pii t_p = p;int t_ans = ans;
      |       ^~~
cvenk.cpp:181:19: warning: unused variable 't_ans' [-Wunused-variable]
  181 |   pii t_p = p;int t_ans = ans;
      |                   ^~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:19:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  #define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
cvenk.cpp:341:5: note: in expansion of macro 'files'
  341 |     files;
      |     ^~~~~
cvenk.cpp:19:51: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  #define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
      |                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:341:5: note: in expansion of macro 'files'
  341 |     files;
      |     ^~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40