Submission #292455

#	Time	Username	Problem	Language	Result	Execution time	Memory
292455		jbroeksteeg	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	350 ms	19448 KiB

ho_t1

#include <iostream>
#include <climits>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <array>
#include <memory>

#define IN(a,b) (a.find(b) != a.end())
#define p(a,b) make_pair(a,b)
#define readVec(a) for (int __i = 0; __i<(int)a.size();__i++){cin>>a[__i];}

// jimjam

template<typename T>
void pMin(T &a, T b) {if (b<a){a=b;}}
template<typename T>
void pMax(T &a, T b) {if (b>a){a=b;}}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& c);
template<typename A, typename B>
std::ostream& operator<<(std::ostream& os, const std::pair<A,B>& c) {std::cout << "(" << c.first << ", " << c.second << ")";return os;}

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	vector<pair<int,int>> ties(n+1), people(n);
	for (int i = 0; i < n + 1; i++) {
		cin >> ties[i].first;
		ties[i].second = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> people[i].first;
		people[i].second = i;
	}
	sort(ties.begin(),ties.end());
	sort(people.begin(),people.end());
	vector<int> answer(n+1, INT_MAX);
	
//	for (int i = 0; i < 10; i++) {
//		int l = 0;
//		for (int j = 0; j < 9; j++) {
//			if (l==i) l++;
//			cout << j << ":" << l << ", ";
//			l++;
//		}
//		cout << endl;
//	}
	// initially, take the first one 
	// max of (tie - person)
	
	multiset<int> current;
	for (int i = 0; i < n; i++) {
		current.insert( max(ties[i+1].first - people[i].first, 0) );
	}
	answer[ ties[0].second ] = *prev(current.end());

	for (int i = 1; i <= n; i++) {
		current.erase(current.find( max(ties[i].first - people[i-1].first, 0) ));
		current.insert(ties[i-1].first-people[i-1].first);
		answer[ ties[i].second ] = *prev(current.end());
	}
	for (int i: answer) cout << i << " ";
	cout << endl;

	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91