답안 #42902 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42902	2018-03-06T08:44:59 Z	arafat_01	Cultivation (JOI17_cultivation)	C++14	5 / 100	2000 ms	748 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 (true) {
		srand (time (NULL));
		int can = 25, ans = rand () % 10 + 5;
		while (clock()/(double)CLOCKS_PER_SEC <= 1.8) {
			int len = rand () % can + 1;
			cool = 0;
			rec (1, len);
			if (cool) can = min (can, len);
		}		
	}
	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	1800 ms	356 KB	Output is correct
2	Correct	1800 ms	424 KB	Output is correct
3	Correct	1800 ms	552 KB	Output is correct
4	Correct	1800 ms	624 KB	Output is correct
5	Correct	1800 ms	624 KB	Output is correct
6	Correct	1800 ms	624 KB	Output is correct
7	Correct	1800 ms	712 KB	Output is correct
8	Correct	1800 ms	712 KB	Output is correct
9	Correct	1800 ms	748 KB	Output is correct
10	Correct	1800 ms	748 KB	Output is correct
11	Correct	1800 ms	748 KB	Output is correct
12	Correct	1800 ms	748 KB	Output is correct
13	Correct	1800 ms	748 KB	Output is correct
14	Correct	1800 ms	748 KB	Output is correct
15	Correct	1802 ms	748 KB	Output is correct
16	Correct	1800 ms	748 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1800 ms	356 KB	Output is correct
2	Correct	1800 ms	424 KB	Output is correct
3	Correct	1800 ms	552 KB	Output is correct
4	Correct	1800 ms	624 KB	Output is correct
5	Correct	1800 ms	624 KB	Output is correct
6	Correct	1800 ms	624 KB	Output is correct
7	Correct	1800 ms	712 KB	Output is correct
8	Correct	1800 ms	712 KB	Output is correct
9	Correct	1800 ms	748 KB	Output is correct
10	Correct	1800 ms	748 KB	Output is correct
11	Correct	1800 ms	748 KB	Output is correct
12	Correct	1800 ms	748 KB	Output is correct
13	Correct	1800 ms	748 KB	Output is correct
14	Correct	1800 ms	748 KB	Output is correct
15	Correct	1802 ms	748 KB	Output is correct
16	Correct	1800 ms	748 KB	Output is correct
17	Execution timed out	2045 ms	748 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1800 ms	356 KB	Output is correct
2	Correct	1800 ms	424 KB	Output is correct
3	Correct	1800 ms	552 KB	Output is correct
4	Correct	1800 ms	624 KB	Output is correct
5	Correct	1800 ms	624 KB	Output is correct
6	Correct	1800 ms	624 KB	Output is correct
7	Correct	1800 ms	712 KB	Output is correct
8	Correct	1800 ms	712 KB	Output is correct
9	Correct	1800 ms	748 KB	Output is correct
10	Correct	1800 ms	748 KB	Output is correct
11	Correct	1800 ms	748 KB	Output is correct
12	Correct	1800 ms	748 KB	Output is correct
13	Correct	1800 ms	748 KB	Output is correct
14	Correct	1800 ms	748 KB	Output is correct
15	Correct	1802 ms	748 KB	Output is correct
16	Correct	1800 ms	748 KB	Output is correct
17	Execution timed out	2045 ms	748 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1800 ms	356 KB	Output is correct
2	Correct	1800 ms	424 KB	Output is correct
3	Correct	1800 ms	552 KB	Output is correct
4	Correct	1800 ms	624 KB	Output is correct
5	Correct	1800 ms	624 KB	Output is correct
6	Correct	1800 ms	624 KB	Output is correct
7	Correct	1800 ms	712 KB	Output is correct
8	Correct	1800 ms	712 KB	Output is correct
9	Correct	1800 ms	748 KB	Output is correct
10	Correct	1800 ms	748 KB	Output is correct
11	Correct	1800 ms	748 KB	Output is correct
12	Correct	1800 ms	748 KB	Output is correct
13	Correct	1800 ms	748 KB	Output is correct
14	Correct	1800 ms	748 KB	Output is correct
15	Correct	1802 ms	748 KB	Output is correct
16	Correct	1800 ms	748 KB	Output is correct
17	Execution timed out	2045 ms	748 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #42902

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