oj.uz

답안 #389125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389125 2021-04-13T16:58:18 Z arwaeystoamneg Hiring (IOI09_hiring) C++17
100 / 100
 949 ms 43044 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353  
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
template<class T>class segment_tree
{
	struct item
	{
		T sum;
	};
	item single(T i)
	{
		return { i };
	}
	item merge(item x, item y)
	{
		item ans;
		ans.sum = x.sum + y.sum;
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0 };
public:void build(vector<T>& B)
{
	int	n = B.size();
	height = log2(n + 1) + 1;
	A.rsz(n);
	tree.rsz((1 << height + 1) - 1);
	F0R(i, n)A[i] = single(B[i]);
	A.rsz(1 << height, neutral);
	build(A, 0, 0, (1 << height) - 1);
}
	  void build(vector<item>& A, int v, int tl, int tr)
	  {
		  if (tl == tr)
			  tree[v] = A[tl];
		  else
		  {
			  int mid = (tl + tr) / 2;
			  build(A, 2 * v + 1, tl, mid);
			  build(A, 2 * v + 2, mid + 1, tr);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
public:T query(int l, int r)
{
	return query(0, 0, (1 << height) - 1, l, r).sum;
}
	  item query(int v, int tl, int tr, int l, int r)
	  {
		  if (r<tl || l>tr)return neutral;
		  if (l <= tl && r >= tr)
		  {
			  return tree[v];
		  }
		  int mid = (tl + tr) / 2;
		  return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	  }
	  //assign
public:void update(int pos, T val)
{
	update(0, 0, (1 << height) - 1, pos, single(val));
}
	  void update(int v, int tl, int tr, int pos, item val)
	  {
		  if (tl == tr)
		  {
			  tree[v] = val;
		  }
		  else
		  {
			  int mid = (tl + tr) / 2;
			  if (pos <= mid)
				  update(2 * v + 1, tl, mid, pos, val);
			  else
				  update(2 * v + 2, mid + 1, tr, pos, val);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
public:int get(T k)
{
	return get(0, 0, (1 << height) - 1, k);
}
	  int get(int v, int tl, int tr, T k)
	  {
		  if (tl == tr)return tl;
		  int mid = (tl + tr) / 2;
		  if (k >= tree[2 * v + 1].sum)
			  return get(2 * v + 2, mid + 1, tr, k - tree[2 * v + 1].sum);
		  return get(2 * v + 1, tl, mid, k);
	  }
};

int n;
const int MAX = 5e5 + 5;
ll w;
int a[MAX], b[MAX], order[MAX], order1[MAX];
int main()
{
	setIO("");
	cin >> n >> w;
	F0R(i, n)cin >> a[i] >> b[i];
	iota(order, order + n, 0);
	sort(order, order + n, [](int i, int j) {return a[j] * b[i] < a[i] * b[j]; });
	iota(order1, order1 + n, 0);
	sort(order1, order1 + n, [](int i, int j) {return b[i] < b[j]; });
	vi temp(n, 1);
	int index[MAX];
	F0R(i, n)index[order1[i]] = i;
	segment_tree<int>active;
	active.build(temp);
	vll temp1(n);
	F0R(i, n)temp1[i] = b[order1[i]];
	segment_tree<ll>cost;
	cost.build(temp1);
	pair< pair<int, ld>, int> ans = { {-inf,-1},-1 };
	F0R(i, n)
	{
		active.update(index[order[i]], 0);
		cost.update(index[order[i]], 0);
		int p = cost.get((w - a[order[i]]) * b[order[i]] / a[order[i]]);
		ll total = cost.query(0, p - 1);
		ld val = a[order[i]] + (ld)a[order[i]] * total / b[order[i]];
		val = w - val;
		ans = max(ans, { {(p == 0 ? -1 : active.query(0, p - 1)) + 1,val},i });
	}
	cout << ans.f.f << endl;
	if (ans.f.f == 0)
	{
		return 0;
	}
//	F0R(i, ans.f)cout << i + 1 << endl;
//	return 0;
	//cout << ans.second << endl;
	int i = ans.s;
	vector<int>x = { order[i] };
	w -= a[order[i]];
	w *= b[order[i]];
	w /= a[order[i]];
	vpi todo;
	FOR(j, i + 1, n)
	{
		todo.pb({ b[order[j]],order[j] });
	}
	sort(all(todo));
	trav(t, todo)
	{
		if (w >= t.f)
		{
			w -= t.f;
			x.pb(t.s);
		}
	}
	sort(all(x));
	if (sz(x) != ans.f.f)assert(0);
	trav(y, x)cout << y + 1 << endl;
}

Compilation message

hiring.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = int]':
hiring.cpp:162:19:   required from here
hiring.cpp:79:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~
hiring.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = long long int]':
hiring.cpp:166:18:   required from here
hiring.cpp:79:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
hiring.cpp: In function 'void setIO(std::string)':
hiring.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:51:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   51 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 528 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 5 ms 844 KB Output is correct
10 Correct 6 ms 844 KB Output is correct
11 Correct 7 ms 912 KB Output is correct
12 Correct 8 ms 1008 KB Output is correct
13 Correct 10 ms 1356 KB Output is correct
14 Correct 15 ms 1500 KB Output is correct
15 Correct 17 ms 1612 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 24 ms 2380 KB Output is correct
5 Correct 84 ms 7572 KB Output is correct
6 Correct 516 ms 32460 KB Output is correct
7 Correct 670 ms 38944 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 10472 KB Output is correct
2 Correct 167 ms 10460 KB Output is correct
3 Correct 163 ms 10456 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 19660 KB Output is correct
2 Correct 278 ms 19836 KB Output is correct
3 Correct 297 ms 19664 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 771 ms 40604 KB Output is correct
2 Correct 757 ms 40636 KB Output is correct
3 Correct 770 ms 40672 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 909 ms 43040 KB Output is correct
2 Correct 894 ms 43040 KB Output is correct
3 Correct 949 ms 43044 KB Output is correct