Submission #515824

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>

using namespace std;

int main()
{
	int n;
	cin >> n;
	// b_tには丸め、その後並び替えた雨の降り始め、降り終わりの時刻のペアが保存される
	vector<pair <int, int> > b_t(30000);
	// tにはb_tのうち被っているものをまとめたペアが保存される(答えになる)
	pair<int, int> t[30000];
	int cnt = 0;
	char ch;
	int tmp, hour, minutes;
	for(int i = 0; i < n; i++){
		cin >> tmp;
		// 条件を満たすように丸める 降り終わりのときだけ分が60になる可能性があるのでそこをなおす
		hour = tmp / 100;
		minutes = tmp % 100;
		minutes -= minutes % 5;
		b_t[i].first = hour * 60 + minutes;
		cin >> ch;
		cin >> tmp;
		hour = tmp / 100;
		minutes = tmp % 100;
		if(minutes % 5 != 0) minutes += (5 - minutes % 5);
		if(minutes >= 60){
			hour++;
			minutes  =minutes % 60;
		}
		b_t[i].second = hour * 60 + minutes;
	}
	sort(b_t.begin(), b_t.begin() + n);
	for(int i = 0; i < n; i++){
		int start = b_t[i].first;
		int end = b_t[i].second;
		if(cnt != 0){
			// これから考えるペアとtの最後尾のペアで重なっている部分があるか調べる
			int startt = max(t[cnt - 1].first, start);
			int endt = min(t[cnt - 1].second, end);
			if(endt - startt >= 0){
				// 重なっているのでt[cnt-1]を書き換える
				t[cnt - 1].second = max(t[cnt - 1].second, end);
			} else {
				// 重なっていないときは新しいペアをつくる
				t[cnt].first = start;
				t[cnt].second = end;
				cnt++;
			}
		} else {
			t[cnt].first = start;
			t[cnt].second = end;
			cnt++;
		}
	}
	for(int i = 0; i < cnt; i++){
		cout.width(4);
		cout.fill('0');
		cout << t[i].first / 60 * 100 + t[i].first % 60 << '-' << t[i].second / 60 * 100 + t[i].second % 60 << endl; 
	}
	return 0;
}

Submission Info

Judge Result