oj.uz

Submission #42909

# Submission time Handle Problem Language Result Execution time Memory
42909 2018-03-06T09:33:39 Z arafat_01 Cultivation (JOI17_cultivation) C++14
5 / 100
 29 ms 748 KB 
#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 (pow (4, len) * n >= 100000) 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

cultivation.cpp: In function 'int main()':
cultivation.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);
                              ^
cultivation.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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 672 KB Output is correct
13 Correct 1 ms 672 KB Output is correct
14 Correct 1 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 672 KB Output is correct
13 Correct 1 ms 672 KB Output is correct
14 Correct 1 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct
17 Incorrect 29 ms 672 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 672 KB Output is correct
13 Correct 1 ms 672 KB Output is correct
14 Correct 1 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct
17 Incorrect 29 ms 672 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 672 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 1 ms 672 KB Output is correct
12 Correct 1 ms 672 KB Output is correct
13 Correct 1 ms 672 KB Output is correct
14 Correct 1 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct
17 Incorrect 29 ms 672 KB Output isn't correct
18 Halted 0 ms 0 KB -