| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846297 |
2023-09-07T13:18:04 Z |
vjudge1 |
ČVENK (COI15_cvenk) |
C++17 |
|
3000 ms |
75288 KB |
// 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;
}
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;
}
if(b.ff == 0){
while(minBit(a.ff)>0 && minBit(a.ff)<minBit(a.ss)) {a.ff-=minBit(a.ff);DEBUGVOID(a.ff);}
return a==b;
}
if(b.ss == 0){
while(minBit(a.ss)>0 && minBit(a.ss)<minBit(a.ss)) {a.ss-=minBit(a.ss);DEBUGVOID(a.ss);}
return a==b;
}
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);}
while(minBit(b.ff)>0 && minBit(b.ff)<minBit(b.ss)) {b.ff-=minBit(b.ff);DEBUGVOID(b.ff);}
return a==b;
}
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);
while(minBit(a.ss)>0 && minBit(b.ff)>minBit(b.ss)) b.ss-=minBit(b.ss);
return a==b;
}
}
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){
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);
forn(i,32){
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;
DEBUGVOID(p);
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 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;
while(l<r){
int mans0 = calcTot(a,m-1,o);
int mans1 = calcTot(a,m,o);
int mans2 = calcTot(a,m+1,o);
if(mans1<mans0 || mans2<mans1) l=m;
if(mans1<mans2 || mans0<mans1) r=m;
if(mans0==mans1 || mans1==mans2) return m;
m = (r+l)/2;
if(m==oldM) {
if(mans0<mans1) return m-1;
if(mans2<mans1) return m+1;
return m;
}
oldM=m;
}
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;
while(l<r){
int mans0 = calcTot(a,o,m-1);
int mans1 = calcTot(a,o,m);
int mans2 = calcTot(a,o,m+1);
if(mans1<mans0 || mans2<mans1) l=m;
if(mans1<mans2 || mans0<mans1) r=m;
if(mans0==mans1 || mans1==mans2) return m;
DEBUGV((vector<int>{mans0,mans1,mans2}));
DEBUG(m);
m = (r+l)/2;
if(m==oldM) {
if(mans0<mans1) return m-1;
if(mans2<mans1) return m+1;
return m;
}
oldM=m;
}
return l;
}
int getHowfar(int a, int b){
if(a==0) return 20;
if(a==0) return (int)(1e9+1);
return (a&-a)-(b)%(a&-a)-1;
}
pii getAns(vii& a){
int posX = 0;
int posY = 0;
pair < int , int > oldPos={-1,-1};
int ans = 100000000000000000ll;
while(oldPos.ff!=posX || oldPos.ss != posY){
oldPos = make_pair(posX,posY);
int down=bsDown(a,posX,posX+getHowfar(posX,posY),posY);
int right=bsRight(a,posX,posX+getHowfar(posX,posY),posY);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(((down+i)&(posY+j))==0 && ans>calcTot(a,down+i,posY+j)){
posX=down+i;
ans=calcTot(a,down+i,posY+j);
}
if(((posX+i)&(right+j))==0 && ans>calcTot(a,posX+i,right+j)){
posY=right+j;
ans=calcTot(a,posX+i,right+j);
}
}
}
}
return oldPos;
}
void solve(int _t_case){
DEBUG(isSame({12,3},{9,6}));
int n;
cin >> n;
vii a(n);
for(auto&x:a) cin >> x.ff >> x.ss;
//DEBUG(calcTot(a,a[0].ff,a[0].ss));
pii ans = getAns(a);
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);
}
return 0;
}
Compilation message
cvenk.cpp: In function 'long long int bsDown(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
cvenk.cpp:206:6: warning: unused variable 'lans' [-Wunused-variable]
206 | int lans = calcTot(a,l,o);
| ^~~~
cvenk.cpp:207:6: warning: unused variable 'rans' [-Wunused-variable]
207 | int rans = calcTot(a,r,o);
| ^~~~
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:229:6: warning: unused variable 'lans' [-Wunused-variable]
229 | int lans = calcTot(a,o,l);
| ^~~~
cvenk.cpp:230:6: warning: unused variable 'rans' [-Wunused-variable]
230 | int rans = calcTot(a,o,r);
| ^~~~
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:297:5: note: in expansion of macro 'files'
297 | 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:297:5: note: in expansion of macro 'files'
297 | files;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3027 ms |
75288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3030 ms |
75072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3022 ms |
74828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3035 ms |
74584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
