Submission #1239961


Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	vector<pair<int, int> > v;
	priority_queue<pair<pair<int, int>, int> > qu;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a, b));
		qu.push(make_pair(make_pair(a, b), i));
	}
	pair<int, int> result[1000002];
	// result[i].first : 時刻iから仕事を始めるとした時、
	// 最も多く選ぶ方法において時刻iから始める仕事の番号
	// result[i].second : 時刻iから仕事を始めるとした時、
	// 最も多く選ぶ方法において時刻i以降で行う仕事の個数
	result[1000001] = make_pair(-1, 0);
	for(int i = 1000000; i >= 0; i--){
		result[i] = result[i + 1];
		if(qu.empty()) continue;
		int a = ((qu.top()).first).first;
		int b = ((qu.top()).first).second;
		int num = (qu.top()).second;
		while(a == i){
			// cout << a << " " << b << " " << num << endl;
			if(result[b].second + 1 > result[i].second || (result[b].second + 1 == result[i].second && num < result[i].first)){
				result[i] = make_pair(num, result[b].second + 1);
			}
			qu.pop();
			if(qu.empty()) break;
			a = ((qu.top()).first).first;
			b = ((qu.top()).first).second;
			num = (qu.top()).second;
		}
	}
	cout << result[0].second << endl;
	vector<int> ans;
	int num = result[0].first;
	int b = v[num].second;
	ans.push_back(num + 1);
	num = result[b].first;
	while(num != -1){
		ans.push_back(num + 1);
		b = v[num].second;
		num = result[b].first;
	}
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i];
		if(i == ans.size() - 1) cout << endl;
		else cout << " ";
	}
	return 0;
}

Submission Info

Submission Time
Task C - 仕事計画
User maple
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2016 Byte
Status AC
Exec Time 93 ms
Memory 11148 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 27
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
0.txt AC 5 ms 8064 KB
1.txt AC 5 ms 8064 KB
10.txt AC 5 ms 8064 KB
11.txt AC 5 ms 8064 KB
12.txt AC 6 ms 8064 KB
13.txt AC 6 ms 8064 KB
14.txt AC 6 ms 8064 KB
15.txt AC 6 ms 8064 KB
16.txt AC 6 ms 8064 KB
17.txt AC 6 ms 8064 KB
18.txt AC 59 ms 10124 KB
19.txt AC 64 ms 10124 KB
2.txt AC 5 ms 8064 KB
20.txt AC 82 ms 10124 KB
21.txt AC 57 ms 10124 KB
22.txt AC 66 ms 10124 KB
23.txt AC 93 ms 11148 KB
3.txt AC 5 ms 8064 KB
4.txt AC 5 ms 8064 KB
5.txt AC 5 ms 8064 KB
6.txt AC 5 ms 8064 KB
7.txt AC 5 ms 8064 KB
8.txt AC 5 ms 8064 KB
9.txt AC 5 ms 8064 KB
sample1.txt AC 5 ms 8064 KB
sample2.txt AC 5 ms 8064 KB
sample3.txt AC 5 ms 8064 KB