Submission #740267

#	Time	Username	Problem	Language	Result	Execution time	Memory
740267		Mans21	Fountain Parks (IOI21_parks)	C++17	15 / 100	695 ms	152376 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define f first
#define s second 
#define ent '\n'
//#define int long long

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

//typedef long double ld;
typedef long long ll;
using namespace std;
 
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}

struct seg{
	int l,r,id;
};

const string out[2]={"NO\n","YES\n"};
const ll dx[]={-1,-1,1,1};  
const ll dy[]={-1,1,-1,1};
const ll dxx[]={0,0,2,-2};
const ll dyy[]={2,-2,0,0};
const int md=998244353;
const int mod=1e9+7;
const int mx=8e5+12; 
const int tst=1e5;
const bool T=0;

pair<int,pair<int,int>> p[mx];
map<int,bool> used[mx];
map<int,int> pos[mx];
vector<int> g[mx];
int ma[mx];
int mi[mx];

void dfs(int x,int y){
	used[x][y]=1;
	ma[x]=max(ma[x],y);
	mi[x]=min(mi[x],y);
	for(int k=0;k<4;k++){
		int x1=x+dxx[k];
		int y1=y+dyy[k];
		if(!used[x1].count(y1) && pos[x1].count(y1))dfs(x1,y1);
	}
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n=x.size();
	for(int i=1;i<=n;i++){
		p[i]={x[i-1],{y[i-1],i}};
	}
	srand(time(0));
	sort(p+1,p+n+1);
	int mx=0;
	reverse(x.begin(),x.end());
	reverse(y.begin(),y.end());
	x.push_back(0);
	y.push_back(0);
	reverse(x.begin(),x.end());
	reverse(y.begin(),y.end());
	for(int i=1;i<=n;i++){
		mx=max(mx,x[i]);
		pos[x[i]][y[i]]=i-1;
	}
	for(int i=0;i<=mx;i++)mi[i]=1e9;
	dfs(x[1],y[1]);
	for(int i=1;i<=n;i++){
		if(!used[x[i]][y[i]]){
			return 0;
		}
	}
	vector<int> u,v,a,b;
	if(mx==2){
		for(int i=mi[2];i<ma[2];i+=2){
			u.push_back(pos[2][i]);
			v.push_back(pos[2][i+2]);
			a.push_back(1);
			b.push_back(i+1);
		}
		build(u,v,a,b);
		return 1;
	}
	if(mx==4){
		if(!ma[2]){
			for(int i=mi[4];i<ma[4];i+=2){
				u.push_back(pos[4][i]);
				v.push_back(pos[4][i+2]);
				a.push_back(3);
				b.push_back(i+1);
			}
			build(u,v,a,b);
			return 1;
		}
		for(int i=1;i<=n;i++){
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				if(x[i]==2)a.push_back(1);
				else a.push_back(5);
				b.push_back(y[i]+1);
			}
		}
		for(int i=1;i<=n;i++){
			if(x[i]!=2)continue;
			if(pos[4].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[4][y[i]]);
				a.push_back(3);
				b.push_back(y[i]-1);
			}
		}
		build(u,v,a,b);
		return 1;
	}
	while(!u.size()){
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					a.push_back(x[i]+1);
				}
				else if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1];
					a.push_back(x[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					a.push_back(x[i]+1);
				}
				else if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1];
					a.push_back(x[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1]=1;
					a.push_back(x[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1];
					a.push_back(x[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1]=1;
					a.push_back(x[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1];
					a.push_back(x[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					a.push_back(x[i]+1);
				}
				else if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1];
					a.push_back(x[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					a.push_back(x[i]+1);
				}
				else if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1];
					a.push_back(x[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1]=1;
					a.push_back(x[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1];
					a.push_back(x[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
		random_shuffle(p+1,p+n+1);
		for(int i=1;i<=n;i++){
			int daun=i;
			i=p[i].s.s;
			if(pos[x[i]+2].count(y[i])){
				u.push_back(i-1);
				v.push_back(pos[x[i]+2][y[i]]);
				a.push_back(x[i]+1);
				if(!used[x[i]+1][y[i]-1]){
					used[x[i]+1][y[i]-1]=1;
					b.push_back(y[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1]=1;
					b.push_back(y[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			if(pos[x[i]].count(y[i]+2)){
				u.push_back(i-1);
				v.push_back(pos[x[i]][y[i]+2]);
				b.push_back(y[i]+1);
				if(!used[x[i]-1][y[i]+1]){
					used[x[i]-1][y[i]+1]=1;
					a.push_back(x[i]-1);
				}
				else if(!used[x[i]+1][y[i]+1]){
					used[x[i]+1][y[i]+1];
					a.push_back(x[i]+1);
				}
				else{
					v.clear();
					u.clear();
					a.clear();
					b.clear();
					break;
				}
			}
			i=daun;
		}
		for(int i=1;i<=mx;i++)used[i].clear();
		if(u.size())break;
	}
	build(u,v,a,b);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:312:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  312 |   if(u.size())break;random_shuffle(p+1,p+n+1);
      |   ^~
parks.cpp:312:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  312 |   if(u.size())break;random_shuffle(p+1,p+n+1);
      |                     ^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30