Submission #1046663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046663		Edu175	Shortcut (IOI16_shortcut)	C++17	97 / 100	2083 ms	158260 KiB

shortcut

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto dkfjhg:v)cout<<dkfjhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("avx2,bmi,bmi2,popcnt,lzcnt")
random_device rd;
mt19937 rng(rd());
const ll INF=1e16;
int n,c;
vector<ll>p,d;
ii operator^(ii a, ii b){
	return {max(a.fst,b.fst),min(a.snd,b.snd)};
}

ll cuenta(int i, bool b){
	return d[i]+(b?-1:1)*p[i];
}
bool les(int i, int j, bool b){
	if(i==-1)return 1;
	if(j==-1)return 0;
	return cuenta(i,b)<cuenta(j,b);
}
ii oper(ii a, ll i, ll w){
	if(les(a.fst,i,w))a.snd=a.fst,a.fst=i;
	else if(les(a.snd,i,w))a.snd=i;
	return a;
}
vector<ii> mn,mx;
vector<ll>sums; vector<int>ids,per;
bool can(ll m){
	vector<ii>ed;
	auto add=[&](int i, int j){
		if(i>j)swap(i,j);
		if(i!=-1)ed.pb({i,j});
	};
	int pos=0;
	for(auto i:ids){
		while(pos<n&&sums[pos]<=m+p[i]-d[i])pos++;
		if(pos<n){
			ll j=mn[pos].fst;
			if(j==i)j=mn[pos].snd;
			add(i,j);
			
			j=mx[pos].fst;
			if(j==i)j=mx[pos].snd;
			add(i,j);
		}
	}
	
	// if(m==fake){
	// 	for(auto [i,j]:ed)cout<<i<<","<<j<<" ";;cout<<"\n";
	// }
	
	ii xc={-INF,INF},yc=xc;
	for(auto [i,j]:ed){
		ll s=m-c-d[i]-d[j];
		ii x={p[i]+p[j]-s,p[i]+p[j]+s};
		ii y={p[i]-p[j]-s,p[i]-p[j]+s};
		// if(m==fake)cout<<s<<" "<<x.fst<<","<<x.snd<<" "<<y.fst<<","<<y.snd<<" s x y\n";
		xc=xc^x;
		yc=yc^y;
	}
	// if(m==fake)cout<<xc.fst<<","<<xc.snd<<" "<<yc.fst<<","<<yc.snd<<" xc yc\n";
	for(auto i:per){
		ii pa=ii({xc.fst-p[i],xc.snd-p[i]})^
			   ii({p[i]-yc.snd,p[i]-yc.fst});
		// if(m==fake){
		// 	cout<<pa.fst<<","<<pa.snd<<"\n";
		// }
		auto it=lower_bound(ALL(p),pa.fst);
		if(it!=p.end()&&*it<=pa.snd)return 1;
	}
	return 0;
}
long long find_shortcut(int N, std::vector <int> L, std::vector <int> D, int C){
	n=N,c=C;
	vector<int>a;
	for(auto i:L)a.pb(i);
	for(auto i:D)d.pb(i);
	
	p=vector<ll>(n);
	fore(i,1,n)p[i]=p[i-1]+a[i-1];
	
	mn=mx=vector<ii>(n);
	vector<int>idx(n);
	iota(ALL(idx),0);
	fore(i,0,n)sums.pb(p[i]+d[i]);
	sort(ALL(idx),[&](int i, int j){return sums[i]<sums[j];});
	sort(ALL(sums));
	
	ids=per=vector<int>(n);
	iota(ALL(ids),0);
	sort(ALL(ids),[&](int i, int j){return p[i]-d[i]<p[j]-d[j];});
	
	for(int i=n-1;i>=0;i--){
		mn[i]=mx[i]={idx[i],-1};
		if(i<n-1){
			mn[i]=oper(mn[i+1],idx[i],0);
			mx[i]=oper(mx[i+1],idx[i],1);
		}
	}
	// for(auto i:mx)cout<<i.fst<<","<<i.snd<<" ";;cout<<"\n";
	// for(auto i:mn)cout<<i.fst<<","<<i.snd<<" ";;cout<<"\n";
	iota(ALL(per),0);
	shuffle(ALL(per),rng);
	ll l=0,r=INF;
	while(l<=r){
		ll m=(l+r)/2;
		if(can(m))r=m-1;
		else l=m+1;
	}
	return l;
}

Compilation message (stderr)

shortcut.cpp:14:50: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
   14 | #pragma GCC optimize("avx2,bmi,bmi2,popcnt,lzcnt")
      |                                                  ^
shortcut.cpp:14:50: warning: bad option '-fbmi' to pragma 'optimize' [-Wpragmas]
shortcut.cpp:14:50: warning: bad option '-fbmi2' to pragma 'optimize' [-Wpragmas]
shortcut.cpp:14:50: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
shortcut.cpp:14:50: warning: bad option '-flzcnt' to pragma 'optimize' [-Wpragmas]
shortcut.cpp:20:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   20 | ii operator^(ii a, ii b){
      |                        ^
shortcut.cpp:20:24: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:20:24: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:20:24: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:20:24: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:24:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   24 | ll cuenta(int i, bool b){
      |                        ^
shortcut.cpp:24:24: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:24:24: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:24:24: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:24:24: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:27:30: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   27 | bool les(int i, int j, bool b){
      |                              ^
shortcut.cpp:27:30: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:27:30: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:27:30: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:27:30: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:32:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   32 | ii oper(ii a, ll i, ll w){
      |                         ^
shortcut.cpp:32:25: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:32:25: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:32:25: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:32:25: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:39:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   39 | bool can(ll m){
      |              ^
shortcut.cpp:39:14: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:39:14: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:39:14: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:39:14: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp: In function 'bool can(ll)':
shortcut.cpp:41:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   41 |  auto add=[&](int i, int j){
      |                           ^
shortcut.cpp:41:27: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:41:27: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:41:27: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:41:27: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp: At global scope:
shortcut.cpp:84:79: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   84 | long long find_shortcut(int N, std::vector <int> L, std::vector <int> D, int C){
      |                                                                               ^
shortcut.cpp:84:79: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:84:79: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:84:79: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:84:79: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:97:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   97 |  sort(ALL(idx),[&](int i, int j){return sums[i]<sums[j];});
      |                                ^
shortcut.cpp:97:32: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:97:32: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:97:32: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:97:32: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:102:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  102 |  sort(ALL(ids),[&](int i, int j){return p[i]-d[i]<p[j]-d[j];});
      |                                ^
shortcut.cpp:102:32: warning: bad option '-fbmi' to attribute 'optimize' [-Wattributes]
shortcut.cpp:102:32: warning: bad option '-fbmi2' to attribute 'optimize' [-Wattributes]
shortcut.cpp:102:32: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
shortcut.cpp:102:32: warning: bad option '-flzcnt' to attribute 'optimize' [-Wattributes]

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3