답안 #42901 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42901	2018-03-06T08:43:05 Z	arafat_01	Cultivation (JOI17_cultivation)	C++14	5 / 100	2000 ms	704 KB

cultivation

#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;
	if (r * c >= 20) {
		srand (time (NULL));
		int can = 25, ans = rand () % 10 + 5;
		while (clock()/(double)CLOCKS_PER_SEC <= 1.85) {
			int len = rand () % can + 1;
			cool = 0;
			rec (1, len);
			if (cool) can = min (can, len);
		}		
	}
	for (int len = 1;len <= 16;len ++) {
		cool = 0;
		rec (1, len);
		if (cool) {
			printf ("%d", len);
			return 0;
		} 
		n = was;
	}
 	return 0;                                                  	
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:118:17: warning: unused variable 'ans' [-Wunused-variable]
   int can = 25, ans = rand () % 10 + 5;
                 ^
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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	532 KB	Output is correct
4	Correct	2 ms	532 KB	Output is correct
5	Correct	1 ms	532 KB	Output is correct
6	Correct	2 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	1 ms	532 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	2 ms	676 KB	Output is correct
11	Correct	1 ms	676 KB	Output is correct
12	Correct	1 ms	676 KB	Output is correct
13	Correct	1 ms	676 KB	Output is correct
14	Correct	1 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	1 ms	676 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	532 KB	Output is correct
4	Correct	2 ms	532 KB	Output is correct
5	Correct	1 ms	532 KB	Output is correct
6	Correct	2 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	1 ms	532 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	2 ms	676 KB	Output is correct
11	Correct	1 ms	676 KB	Output is correct
12	Correct	1 ms	676 KB	Output is correct
13	Correct	1 ms	676 KB	Output is correct
14	Correct	1 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	1 ms	676 KB	Output is correct
17	Execution timed out	2052 ms	676 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	532 KB	Output is correct
4	Correct	2 ms	532 KB	Output is correct
5	Correct	1 ms	532 KB	Output is correct
6	Correct	2 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	1 ms	532 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	2 ms	676 KB	Output is correct
11	Correct	1 ms	676 KB	Output is correct
12	Correct	1 ms	676 KB	Output is correct
13	Correct	1 ms	676 KB	Output is correct
14	Correct	1 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	1 ms	676 KB	Output is correct
17	Execution timed out	2052 ms	676 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	704 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	704 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	532 KB	Output is correct
4	Correct	2 ms	532 KB	Output is correct
5	Correct	1 ms	532 KB	Output is correct
6	Correct	2 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	1 ms	532 KB	Output is correct
9	Correct	1 ms	532 KB	Output is correct
10	Correct	2 ms	676 KB	Output is correct
11	Correct	1 ms	676 KB	Output is correct
12	Correct	1 ms	676 KB	Output is correct
13	Correct	1 ms	676 KB	Output is correct
14	Correct	1 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	1 ms	676 KB	Output is correct
17	Execution timed out	2052 ms	676 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #42901

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0