답안 #1111593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111593	2024-11-12T09:51:34 Z	YSH2020	Fire (BOI24_fire)	C++17	21 / 100	357 ms	6612 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> shifts;
	int max_dist = 0;
	int start_x = 0;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		if (x > y) y += m;
		if (y-x > max_dist) {max_dist = y-x;start_x = x;}
		shifts.push_back({x, y});
	}
	for (int i=0; i < n; i++) {
		shifts[i] = {(shifts[i].first-start_x+2*m)%m, (shifts[i].second-start_x+2*m)%m};
		if (shifts[i].first > shifts[i].second) shifts[i]={shifts[i].first, shifts[i].second+m};
	}
	sort(shifts.begin(), shifts.end());
	if (n > 5000) {
			int time = 0;
	int furthest_time = 0;
	int c = 0;
	for (int i=0; i < n; i++) {
		if (shifts[i].first <= time) furthest_time = max(furthest_time, shifts[i].second);
		else {
			c++;
			time = furthest_time;
			if (time >= m) {cout << c; return 0;}
			if (shifts[i].first > time) {cout << -1; return 0;}
			furthest_time = shifts[i].second;
		}
	}
	c++;
	time = furthest_time;
	if (time >= m) {cout << c; return 0;}
	else cout << -1;
	}
	else {
		//brute force
			int ans = 10000000;

		for (int t = 0; t < n; t++) {
			int tmp = shifts[1].first;
			for (int i=0; i < n; i++) {
		shifts[i] = {(shifts[i].first-tmp+2*m)%m, (shifts[i].second-tmp+2*m)%m};
		if (shifts[i].first > shifts[i].second) shifts[i]={shifts[i].first, shifts[i].second+m};
	}
	sort(shifts.begin(), shifts.end());
int time = 0;
	int furthest_time = 0;
	int c = 0;
	for (int i=0; i < n; i++) {
		if (shifts[i].first <= time) furthest_time = max(furthest_time, shifts[i].second);
		else {
			c++;
			time = furthest_time;
			if (time >= m) {ans = min(ans, c); break;}
			if (shifts[i].first > time) {cout << -1; return 0;}
			furthest_time = shifts[i].second;
		}
	}
	c++;
	time = furthest_time;
	if (time >= m) {ans = min(ans, c);}
	}if (ans == 10000000) cout << -1; else cout << ans;
		} 
	}

Subtask #1

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	2 ms	336 KB	Output is correct
9	Correct	2 ms	336 KB	Output is correct
10	Correct	2 ms	336 KB	Output is correct
11	Correct	2 ms	336 KB	Output is correct
12	Correct	357 ms	632 KB	Output is correct
13	Correct	318 ms	592 KB	Output is correct
14	Correct	320 ms	592 KB	Output is correct
15	Correct	43 ms	6592 KB	Output is correct
16	Correct	91 ms	6584 KB	Output is correct
17	Correct	111 ms	6576 KB	Output is correct
18	Correct	120 ms	6596 KB	Output is correct
19	Correct	115 ms	6612 KB	Output is correct
20	Correct	114 ms	6584 KB	Output is correct

Subtask #6

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Halted	0 ms	0 KB	-