Submission #543511

# Submission time Handle Problem Language Result Execution time Memory
543511 2022-03-30T19:44:56 Z brunnorezendes Fountain Parks (IOI21_parks) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#define s second
#define f first

using namespace std;

typedef vector <int> vi;
typedef pair<int, int> ii;
typedef pair<ii, ii> iiii;
typedef vector<ii> vii;
typedef map <pair<int,int>, int > mpair;

mpair mp,  match1;
vi adjx, adjy, brenchx, brenchy;
vii match2;

void build(vi x, vi y, vi a, vi b){
	cout << "[";
	int i, n=x.size();
	for(i=0;i<n;i++){
		cout << x[i] << " ";
	}
	cout << "]";
	cout << endl;
	cout << "[";
	for(i=0;i<n;i++){
		cout << y[i] << " ";
	}
	cout << "]";
	cout << endl;
	cout << "[";
	for(i=0;i<n;i++){
		cout << a[i] << " ";
	}
	cout << "]";
	cout << endl;
	cout << "[";
	for(i=0;i<n;i++){
		cout << b[i] << " ";
	}
	cout << "]";
	cout << endl;
}

iiii find(int u, vi x, vi y){
	ii c, d;
	iiii e;
	int i = adjx[u], j = adjy[u];
	if(x[i]==x[j]){
		c = {x[i]+1, (y[i]+y[j])/2};
		d = {x[i]-1, (y[i]+y[j])/2};
		e = {c, d};
		return (e);
	}
	else{
		c = {(x[i]+x[j])/2, y[i]+1};
		d = {(x[i]+x[j])/2, y[i]-1};
		e = {c, d};
		return (e);
	}
}

int matching(int u, vi x, vi y){
	iiii retur;
	ii op1, op2;
	retur = find(u, x, y);
	op1 = retur.f;
	op2 = retur.s;
	if(!match1[op1]){
		match1[op1] = u+1;
		match2[u] = op1;
		return 1;
	}
	else if(!match1[op2]){
		match1[op2] = u+1;
		match2[u] = op2;
		return 1;
	}
	else{
		if((match1[op1] != u+1) && (match1[op2] != u+1)){
			return 0;
		}
		if(match1[op2]==u+1) swap(op1, op2);
		if(matching(match1[op2]-1, x, y)){
			match1[op2] = u+1;
			match2[u] = op2;
			return 1;
		}
	}
}

int maskx[4], masky[4];

int construct_roads(vi x, vi y){
	maskx[1] = 2; maskx[3] = -2;
	masky[0] = 2; masky[2] = -2;
	int n = x.size(), i, a, j;
	match2 = vii(n, {-1, -1});
	for(i=0;i<n;i++){
		mp[{x[i], y[i]}] = i+1;
	}
	for(i=0;i<n;i++){
		for(j=0;j<4;j++){
			a = mp[{x[i]+maskx[j], y[i]+masky[j]}];
			if(a>i+1){
				a--;
				adjx.push_back(i);
				adjy.push_back(a);
			}
		}
	}
	for(i=0;i<adjx.size();i++){
		if(!matching(i, x, y)) return 0;
	}
	for(i=0;i<adjx.size();i++){
		brenchx.push_back(match2[i].f);
		brenchy.push_back(match2[i].s);
	}
	build(adjx, adjy, brenchx, brenchy);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:112:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(i=0;i<adjx.size();i++){
      |          ~^~~~~~~~~~~~
parks.cpp:115:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(i=0;i<adjx.size();i++){
      |          ~^~~~~~~~~~~~
parks.cpp: In function 'int matching(int, vi, vi)':
parks.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^
/usr/bin/ld: /tmp/cc0dB1lY.o: in function `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x270): multiple definition of `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/ccqoXqBX.o:parks.cpp:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status