Submission #436573

#	Time	Username	Problem	Language	Result	Execution time	Memory
436573		Apiram	Fountain Parks (IOI21_parks)	C++17	5 / 100	3597 ms	14064 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct point {
	int x,y,index;
};
bool dist(point x,point y){
	if (pow(x.x - y.x,2)+pow(x.y-y.y,2)!=4)return false;
	return true;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<point>arr;
    int n = x.size();
    bool ok=true;
    
    for (int i = 0 ;i<n;++i){
    	if (x[i]!=x[0])ok=false;
    	arr.push_back({x[i],y[i],i});
    }
    vector<int>ansx,ansy,ansxi,ansyi;
    if (ok){
    sort(arr.begin(),arr.end(),[&](point a,point b){
    	return a.y<b.y;
    });
    
    for (int i = 1;i<n;++i){
    	if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y)+1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    	}
    	else return 0;
    }
    build(ansxi,ansyi,ansx,ansy);
    return 1;}
    else{
    	set<pair<int,int>>p;
    	sort(arr.begin(),arr.end(),[&](point a,point b){
    		if (a.x==b.x)return a.y<b.y;
    		return a.x<b.x;
    });
    vector<int>checkother;
    	int i =1;
    	for (;i<n;++i){
    		if (arr[i].x!=2)break;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) - 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		p.insert({ansx.back(),ansy.back()});
    		}
    		else checkother.push_back(i);
    	}
    	checkother.push_back(i);
    	for (;i<n;++i){
    		if (arr[i-1].x==2)continue;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		p.insert({ansx.back(),ansy.back()});
    		}
    		else checkother.push_back(i);
    	}
    	
    	bool okay=true;
    	set<int>got;
sort(checkother.begin(),checkother.end());
    for (auto y:checkother){
    	if (got.find(y)!=got.end())continue;
    	bool ok=false;
    	int j = y+1;
    for (int i = 0;i<n;++i){
    	if (dist(arr[j-1],arr[i])){
    		int first1=min(arr[i].x,arr[j-1].x) + 1;
    		int first2=min(arr[i].x,arr[j-1].x) - 1;
    		int second1=min(arr[i].y,arr[j-1].y) + 1;
    		int second2 = min(arr[i].y,arr[j-1].y) - 1;
    		if (p.find({first1,second1})==p.end()){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second1);
    			ansxi.push_back(arr[j-1].index);
    			ansyi.push_back(arr[i].index);
    			p.insert({ansx.back(),ansy.back()});
    			got.insert(i);
    			break;
    		}
    		if (p.find({first2,second1})==p.end()){
    			ok=true;
    			ansx.push_back(first2);
    			ansy.push_back(second1);
    			ansxi.push_back(arr[j-1].index);
    			ansyi.push_back(arr[i].index);
    			p.insert({ansx.back(),ansy.back()});
    			got.insert(i);
    			break;
    		}
    		if (p.find({first1,second2})==p.end()){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second2);
    			ansxi.push_back(arr[j-1].index);
    			ansyi.push_back(arr[i].index);
    			p.insert({ansx.back(),ansy.back()});
    			got.insert(i);
    			break;
    		}
    		if (p.find({first2,second2})==p.end()){
    			ok=true;
    			ansx.push_back(first2);
    			ansy.push_back(second2);
    			ansxi.push_back(arr[j-1].index);
    			ansyi.push_back(arr[i].index);
    			p.insert({ansx.back(),ansy.back()});
    			got.insert(i);
    			break;
    		}
    		
    		
    	}
    }
    if (!ok){
    	okay=false;
    	break;
    }
    }
   if (!okay)return 0;
    	  build(ansxi,ansyi,ansx,ansy);
    	  return 1;
    }
    
    
}

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