제출 #846424

#제출 시각아이디문제언어결과실행 시간메모리
846424vjudge1ČVENK (COI15_cvenk)C++17
0 / 100
3096 ms71320 KiB
// 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; }

컴파일 시 표준 에러 (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;
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...