Submission #679060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
679060	2023-01-07T11:00:59 Z	vjudge1	Sailing Race (CEOI12_race)	C++17	0 / 100	255 ms	8580 KB

race

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;


int n, k, dp[MAXN][MAXN][2], ans;
vector<int> adj[MAXN];
bool bio[MAXN];
int cur_i, cur_j, cur_b;
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
		int x; cin >> x;
		while(x){
			--x;
			adj[x].push_back(i);
			adj[x].push_back(i + n);
			adj[x + n].push_back(i);
			adj[x + n].push_back(i + n);
			cin >> x;
		}
	}
	for(int i = 0; i < 2 * n; ++i){
		dp[i][i][0] = dp[i][i][1] = 1;
	}
	for(int off = 1; off < n; ++off){
		for(int i = 0; i < 2 * n - off; ++i){
			int j = i + off;
			for(int x : adj[i]){
				if(i < x && x <= j) dp[i][j][0] = max(dp[i][j][0], max(dp[i + 1][x][1], dp[x][j][0]) + 1);
			}
			for(int x : adj[j]){
				if(i <= x && x < j) dp[i][j][1] = max(dp[i][j][1], max(dp[x][j - 1][0], dp[i][x][1]) + 1);
			}
			ans = max(ans, dp[i][j][0]);
			ans = max(ans, dp[i][j][1]);
		}
	}
	for(int off = 1; off < n; ++off){
		for(int i = 0; i < 2 * n - off; ++i){
			int j = i + off;
			if(max(dp[i][j][0], dp[i][j][1]) == ans){
				cur_i = i; cur_j = j;
				if(dp[i][j][1] == ans) cur_b = 1;
				break;
			}
		}
		if(cur_i != cur_j) break;
	}
	
	while(cur_i != cur_j){
		int val = dp[cur_i][cur_j][cur_b];
		if(cur_b){
			bio[cur_j % n] = 1;
			for(int x : adj[cur_j]){
				if(cur_i <= x && x < cur_j){
					if(dp[cur_i][x][1] + 1 == val){
						cur_j = x; cur_b = 1;
						break;
					}
					if(dp[x][cur_j - 1][0] + 1 == val){
						cur_i = x; --cur_j; cur_b = 0;
						break;
					}
				}
			}
		} else {
			bio[cur_i % n] = 1;
			for(int x : adj[cur_i]){
				if(cur_i < x && x <= cur_j){
					if(dp[cur_i + 1][x][1] + 1 == val){
						++cur_i; cur_j = x; cur_b = 1;
						break;
					}
					if(dp[x][cur_j][0] + 1 == val){
						cur_i = x; cur_b = 0;
						break;
					}
				}
			}
		}
	}
	cur_i %= n;
	bio[cur_i] = 1;
	if(k){
		if(ans == n){
			cout << ans << "\n" << cur_i;
		} else {
			cout << ans + 1 << "\n";
			for(int i = 0; i < n; ++i){
				if(!bio[i]){
					cout << i + 1 << "\n";
				}
			}
		}
	} else {
		cout << ans << "\n" << cur_i;
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Output isn't correct
2	Incorrect	1 ms	456 KB	Output isn't correct
3	Incorrect	1 ms	468 KB	Output isn't correct
4	Incorrect	1 ms	592 KB	Output isn't correct
5	Incorrect	1 ms	724 KB	Output isn't correct
6	Incorrect	2 ms	840 KB	Output isn't correct
7	Incorrect	4 ms	980 KB	Output isn't correct
8	Incorrect	2 ms	980 KB	Output isn't correct
9	Incorrect	4 ms	1236 KB	Output isn't correct
10	Incorrect	11 ms	1492 KB	Output isn't correct
11	Incorrect	6 ms	1364 KB	Output isn't correct
12	Incorrect	18 ms	2516 KB	Output isn't correct
13	Incorrect	31 ms	3944 KB	Output isn't correct
14	Incorrect	61 ms	5588 KB	Output isn't correct
15	Incorrect	210 ms	7916 KB	Output isn't correct
16	Incorrect	196 ms	8440 KB	Output isn't correct
17	Incorrect	155 ms	7932 KB	Output isn't correct
18	Incorrect	71 ms	7492 KB	Output isn't correct
19	Incorrect	255 ms	8580 KB	Output isn't correct
20	Incorrect	233 ms	8512 KB	Output isn't correct