oj.uz

Submission #953087

# Submission time Handle Problem Language Result Execution time Memory
953087 2024-03-25T12:31:27 Z WonderfulWhale IOI Fever (JOI21_fever) C++17
11 / 100
 417 ms 12892 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int n;
namespace B2 {
const int MAXN = 100'009;
 
pii tab[MAXN];
int dis[MAXN];
int dir[MAXN];
vector<int> G[MAXN][4];
 
int f(int a, int b) {
	return tab[a].st-tab[b].st+tab[a].nd-tab[b].nd;
}
 
int dijkstra(int x, int x_dir) {
	fill(dis, dis+n, 1e9);
	int cnt = 0;
	dis[x] = 0;
	dir[x] = x_dir;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({dis[x], x});
	while(sz(Q)) {
		auto [d_x, x] = Q.top();
		Q.pop();
		if(d_x!=dis[x]) continue;
		cnt++;
		for(int y:G[x][dir[x]]) {
			int d = f(x, y);
			if(d>d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				dir[y] = (dir[x]+1)%4;
				Q.push({dis[y], y});
			}
		}
		for(int y:G[x][(dir[x]+1)%4]) {
			int d = f(x, y);
			if(d>d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				int ndir = dir[x]-1;
				if(ndir<0) ndir+=4;
				dir[y] = ndir;
				Q.push({dis[y], y});
			}
		}
	}
	return cnt;
}
}
namespace B1 {

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};


pii tab[10];
int dir[10];
int dis[10];
bool vis[10];

int ans = 0;

int check(int x, int y) {
	int d1 = abs(tab[x].st-tab[y].st);
	int d2 = abs(tab[x].nd-tab[y].nd);
	if(d1!=d2) return -1;
	pii p1 = {tab[x].st+dx[dir[x]]*d1, tab[x].nd+dy[dir[x]]*d1};
	pii p2 = {tab[y].st+dx[dir[y]]*d1, tab[y].nd+dy[dir[y]]*d1};
	if(p1!=p2) return -1;
	return d1;
}

void dijkstra() {
	// for(int i=0;i<n;i++) cerr << dir[i] << " ";
	// cerr << "\n";
	vector<int> v(n-1);
	iota(all(v), 1);
	do {
		int cnt = 1;
		vector<int> d(n-1, 1e9);
		for(int i=0;i<n-1;i++) {
			int x = check(v[i], 0);
			if(x!=-1) {
				d[i] = min(d[i], x);
			}
			for(int j=i-1;j>=0;j--) {
				int y = check(v[i], v[j]);
				if(y<d[j]) continue;
				d[i] = min(d[i], y);
			}
			if(d[i]<1e9) cnt++;
			else break;
		}
		ans = max(ans, cnt);
	} while(next_permutation(all(v)));
}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	if(n<=7) {
	for(int i=0;i<n;i++) {
		cin >> B1::tab[i].st >> B1::tab[i].nd;
	}
	for(int i=0;i<(1<<(2*n));i++) {
		for(int j=0;j<2*n;j+=2) {
			bool a = i&(1<<j);
			bool b = i&(1<<(j+1));
			B1::dir[j/2] = 2*a+b;
		}
		B1::dijkstra();
	}
	cout << B1::ans << "\n";
	return 0;
	}
	using namespace B2;
	for(int i=0;i<n;i++) {
		int a, b;
		cin >> a >> b;
		tab[i] = {a-b, a+b};
		// cerr << i << ": " << tab[i] << "\n";
	}
	for(int i=0;i<n;i++) {
		auto [a1, b1] = tab[i];
		for(int j=0;j<n;j++) {
			auto [a2, b2] = tab[j];
			if(a1>a2&&b1==b2) {
				G[i][0].pb(j);
			}
			if(a1==a2&&b2>b1) {
				G[i][1].pb(j);
			}
			if(a1<a2&&b1==b2) {
				G[i][2].pb(j);
			}
			if(a1==a2&&b2<b1) {
				G[i][3].pb(j);
			}
		}
	}
	int ans = 0;
	for(int i=0;i<4;i++) {
		ans = max(ans, dijkstra(0, i));
	}
	cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 4 ms 10864 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 13 ms 11096 KB Output is correct
14 Correct 14 ms 10896 KB Output is correct
15 Correct 13 ms 10844 KB Output is correct
16 Correct 285 ms 10864 KB Output is correct
17 Correct 293 ms 10844 KB Output is correct
18 Correct 258 ms 11088 KB Output is correct
19 Correct 260 ms 10872 KB Output is correct
20 Correct 417 ms 11092 KB Output is correct
21 Correct 262 ms 10840 KB Output is correct
22 Correct 284 ms 10848 KB Output is correct
23 Correct 264 ms 11096 KB Output is correct
24 Correct 300 ms 10868 KB Output is correct
25 Correct 312 ms 11088 KB Output is correct
26 Correct 298 ms 10868 KB Output is correct
27 Correct 306 ms 11088 KB Output is correct
28 Correct 279 ms 10876 KB Output is correct
29 Correct 269 ms 10844 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 297 ms 10868 KB Output is correct
32 Correct 277 ms 10868 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -