Submission #100285

#	Time	Username	Problem	Language	Result	Execution time	Memory
100285		Ort	Konj (COCI19_konj)	C++11	70 / 70	167 ms	27020 KiB

konj

#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cctype>
#include<tuple>
#define MAX 310

using namespace std;

char horse[MAX][MAX];
vector<tuple<int,int,int,int> > mat[MAX][MAX];
vector<pair<int,int> > points;
vector<int> visited[MAX][MAX];
int n, si, sj, a, b, c, d, e, f, g, h;
int maxi, maxj;

void load() {
	int ai, bi, ci, di;
	for(int i=0;i<n;i++) {
		cin >> ai >> bi >> ci >> di;
		mat[bi][ai].push_back(make_tuple(di,ci,bi,ai));
		mat[di][ci].push_back(make_tuple(bi,ai,di,ci));
		visited[bi][ai].push_back(0);
		visited[di][ci].push_back(0);
	}
	cin >> si>> sj;
	int u=sj, d=sj, l=si, r=si;
	bool found = 0;
	while(r<=300 && mat[sj][r].size()==0) r++;
	while(l>0 && mat[sj][l].size()==0) l--;
	if(r<=300 && l>0)
		for(int i=0;i<mat[sj][l].size();i++)
			for(int j=0;j<mat[sj][r].size();j++) {
				tie(a, b, c, d) = mat[sj][l][i];
				tie(e, f, g, h) = mat[sj][r][j];
				if(a==g && b==h && e==c && d==f) found = 1;
			}
	if(found) {si = r; return;}
	while(u>0 && mat[u][si].size()==0) u--;
	while(d<=300 && mat[d][si].size()==0) d++;
	if(d<=300 && u>=0)
		for(int i=0;i<mat[u][si].size();i++)
			for(int j=0;j<mat[d][si].size();j++) {
				tie(a, b, c, d) = mat[u][si][i];
				tie(e, f, g, h) = mat[d][si][j];
				if(a==g && b==h && e==c && d==f) found = 1;
			}
	if(found) {sj = u; return;}
}

void dfs(int y, int x) {
	for(int i=0;i<mat[y][x].size();i++) {
		if(visited[y][x][i]==1) continue;
		visited[y][x][i] = 1;
		tie(a, b, c, d) = mat[y][x][i];
		if(a==c) {
			swap(d,b);
			for(int j=b;j<=d;j++) horse[a][j] = '#';
			dfs(a, d);
		}
		else if(b==d) {
			swap(a,c);
			for(int j=a;j<=c;j++) horse[j][b] = '#';
			dfs(c, b);
		}
	}
}

void print_matrix() {
	int minx=1000, miny=1000, maxx=0, maxy=0;
	for(int i=301;i>=0;i--) {
		for(int j=0;j<301;j++) {
			if(horse[i][j]=='#') {
				minx = min(minx, j);
				miny = min(miny, i);
				maxx = max(maxx, j);
				maxy = max(maxy, i);
			}
		}
	}
	for(int i=maxy;i>=miny;i--) {
		for(int j=minx;j<=maxx;j++) {
			cout << horse[i][j];
		}
		cout << "\n";
	}
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<301;i++) for(int j=0;j<301;j++) horse[i][j] = '.';
	cin >> n;
	load();
	dfs(sj,si);
	print_matrix();
	return 0;
}

Compilation message (stderr)

konj.cpp: In function 'void load()':
konj.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<mat[sj][l].size();i++)
               ~^~~~~~~~~~~~~~~~~~
konj.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<mat[sj][r].size();j++) {
                ~^~~~~~~~~~~~~~~~~~
konj.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<mat[u][si].size();i++)
               ~^~~~~~~~~~~~~~~~~~
konj.cpp:44:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<mat[d][si].size();j++) {
                ~^~~~~~~~~~~~~~~~~~
konj.cpp: In function 'void dfs(int, int)':
konj.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<mat[y][x].size();i++) {
              ~^~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 70