답안 #42903 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42903	2018-03-06T08:48:34 Z	arafat_01	Cultivation (JOI17_cultivation)	C++14	5 / 100	2000 ms	692 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 / n >= 4) {
		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);
		}
		cout << can;
		return 0;		
	}
	for (int len = 1;len <= 17;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	1850 ms	248 KB	Output is correct
2	Correct	1850 ms	480 KB	Output is correct
3	Correct	1 ms	480 KB	Output is correct
4	Correct	1850 ms	500 KB	Output is correct
5	Correct	1 ms	500 KB	Output is correct
6	Correct	1850 ms	660 KB	Output is correct
7	Correct	1850 ms	660 KB	Output is correct
8	Correct	1 ms	660 KB	Output is correct
9	Correct	1850 ms	660 KB	Output is correct
10	Correct	1850 ms	676 KB	Output is correct
11	Correct	1850 ms	692 KB	Output is correct
12	Correct	1 ms	692 KB	Output is correct
13	Correct	1850 ms	692 KB	Output is correct
14	Correct	1850 ms	692 KB	Output is correct
15	Correct	1850 ms	692 KB	Output is correct
16	Correct	1850 ms	692 KB	Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	692 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	692 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	1850 ms	248 KB	Output is correct
2	Correct	1850 ms	480 KB	Output is correct
3	Correct	1 ms	480 KB	Output is correct
4	Correct	1850 ms	500 KB	Output is correct
5	Correct	1 ms	500 KB	Output is correct
6	Correct	1850 ms	660 KB	Output is correct
7	Correct	1850 ms	660 KB	Output is correct
8	Correct	1 ms	660 KB	Output is correct
9	Correct	1850 ms	660 KB	Output is correct
10	Correct	1850 ms	676 KB	Output is correct
11	Correct	1850 ms	692 KB	Output is correct
12	Correct	1 ms	692 KB	Output is correct
13	Correct	1850 ms	692 KB	Output is correct
14	Correct	1850 ms	692 KB	Output is correct
15	Correct	1850 ms	692 KB	Output is correct
16	Correct	1850 ms	692 KB	Output is correct
17	Execution timed out	2041 ms	692 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #42903

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