Submission #42906

#	Time	Username	Problem	Language	Result	Execution time	Memory
42906		arafat_01	Port Facility (JOI17_port_facility)	C++14	0 / 100	24 ms	504 KiB

port_facility

#include <stdio.h> 
#include <bits/stdc++.h>

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define prev prv

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e4 + 123;
const int mod = 1e9 + 7;
const double eps = 1e-15;

int r, c, n, d[N], was;
pair < int , int > a[N], b[N];
bool cool, u[55][55];

void go (int& x, int& y, int dir) {
	if (dir == 1) {
		x --;
		if (x < 1) x = 1;
	}
	if (dir == 2) {
		y ++;
		if (y > c) y = c;	
	}
	if (dir == 3) {
		x ++;
		if (x > r) x = r;
	}
	if (dir == 4) {
		y --;
		if (y < 1) y = 1;
	}
}
bool debug;

void korset () {
	cout << "now cordinates: " << n << endl;
	for (int i = 1;i <= n;i ++)
		cout << a[i].F <<  ' ' << a[i].S << endl;
	cout << "--------------------------------------" << endl;
}

void rec (int v, int len) {
	if (cool) return;
	if (v > len) {
		for (int i = 1;i <= r;i ++)
			for (int j = 1;j <= c;j ++)
				u[i][j] = 0;
		n = was;
		for (int i = 1;i <= n;i ++)	u[a[i].F][a[i].S] = 1;
		//if (len == 3 && d[1] == 4 && d[2] == d[3] && d[2] == 3) debug = 1;
		for (int i = 1;i <= len;i ++) {
			if (debug) korset ();
			vector < pair < int , int > > add;
			for (int j = 1;j <= n;j ++) {
				pair < int , int > before = a[j];
				go (a[j].F, a[j].S, d[i]);
				if (!u[a[j].F][a[j].S])
					add.pb (a[j]);
				u[a[j].F][a[j].S] = 1;
				a[j] = before;
			} 
			for (const auto it : add) a[++ n] = it;
		}
		if (debug) {
			cout << endl;
			for (int i = 1;i <= r;i ++, cout << endl)
				for (int j = 1;j <= c;j ++)	cout << u[i][j] << ' ';
			cout << endl;
		}
		debug = 0;
		for (int i = 1;i <= r;i ++)
			for (int j = 1;j <= c;j ++)
				if (!u[i][j]) return;
		cool = 1;
		return;
	}
	d[v] = 1;
	rec (v + 1, len);
	if (cool) return;
	d[v] = 2;
	rec (v + 1, len);
	if (cool) return;
	d[v] = 3;
	rec (v + 1, len);
	if (cool) return;
	d[v] = 4;
	rec (v + 1, len);
	if (cool) return;
}

int main () {
	scanf ("%d%d%d", &r, &c, &n);
	for (int i = 1;i <= n;i ++) {
		scanf ("%d%d", &a[i].F, &a[i].S);	
		b[i] = a[i];
		u[a[i].F][a[i].S] = 1;
	}
	bool dal = 0;
	for (int i = 1;i <= r;i ++)
		for (int j = 1;j <= c;j ++)
			if (!u[i][j]) dal = 1;
	if (!dal) {
		printf ("0");
		return 0;
	}
	was = n;
	int len = 0;
	while (clock () / (double)CLOCKS_PER_SEC <= 1.1) {
		len ++;
		if (len > 10) break;
		cool = 0;
		rec (1, len);
		if (cool) {
			printf ("%d", len);
			return 0;
		} 
		n = was;
	}
	srand (time (NULL));
	cout << rand () % 4 + len;
 	return 0;                                                  	
}
  	

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:101:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &r, &c, &n);
                              ^
port_facility.cpp:103:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a[i].F, &a[i].S); 
                                   ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22