oj.uz

답안 #287452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287452 2020-08-31T17:07:42 Z Namnamseo Teams (CEOI11_tea) C++17
100 / 100
 941 ms 147844 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define data Data

const int max_n = int(1e6) + 10, inf = 1e9;

typedef pair<int,int> pp;
pp data[max_n];
int n;

int dpTN[max_n];
int dpMX[max_n];

struct indi {
	int team_num;
	int max_size;
	int from;
	indi(int a=-1, int b=inf, int c=-1){
		team_num = a; max_size = b; from = c;
	}
	bool operator<(const indi& r) const {
		return make_pair(team_num, -max_size) <
			   make_pair(r.team_num, -r.max_size);
	}
};

const int M =1048576;
indi tree[M<<1];
indi tree_add[M<<1];
indi dp[max_n];
int bef[max_n];

indi getMax(indi* tree, int p){
	indi ret;
	p+=M;
	while(p) ret=max(ret, tree[p]), p>>=1;
	return ret;
}

void upd(indi* tree, int l, int r, indi val){
	l+=M; r+=M;
	while(l<=r){
		if(l%2==1) tree[l]=max(tree[l], val), ++l;
		if(r%2==0) tree[r]=max(tree[r], val), --r;
		l>>=1; r>>=1;
	}
}

vector<vector<int>> ans;

struct cmp {
	bool operator()(const int& a, const int& b){
		return ans[a].size() > ans[b].size();
	}
};
priority_queue<int,vector<int>,cmp> PQ;

int main()
{
    read(n);
    for(int i=1; i<=n; ++i){
		read(data[i].first); data[i].second=i;
    }
    sort(data+1, data+n+1, greater<pp>());
    for(int i=0; i<=n; ++i){
		indi v1 = getMax(tree, i);
		indi v2 = getMax(tree_add, i);
		v2.max_size += i;
		indi my = max(v1, v2);
		if(i == 0) my = indi(0, 0, -1);
		dp[i] = my;
		bef[i] = my.from;
		if(i == n) break;
		if(my.team_num == -1) continue;
		int tn = my.team_num;
		int mt = my.max_size;
		ll pt = tn * 1LL * mt;
		int mv=data[i+1].first;
		upd(tree, i+1, min(pt, ll(n)), indi(tn, mt, -i));
		upd(tree, i+mv, min(i+mt-1, n), indi(tn+1, mt, i));
		upd(tree_add, i+max(mv, mt), n, indi(tn+1, -i, i));
    }
    
    printf("%d\n", dp[n].team_num);
	
	vector<pp> pend;
    int p=n;
    while(p){
		int x=bef[p];
		if(x < 0){
			x=-x;
			for(int i=x+1; i<=p; ++i){
				pend.pb(pp{int(ans.size()), data[i].second});
			}
		} else {
			vector<int> v;
			for(int i=x+1; i<=p; ++i){
				v.pb(data[i].second);
			}
			ans.pb(v);
		}
		p=x;
    }
    int an=ans.size();
    for(int i=an-1; i>=0; --i){
		PQ.push(i);
		while(pend.size()){
			int x, y;
			tie(x, y) = pend.back();
			if(x != i) break;
			pend.pop_back();
			int p=PQ.top(); PQ.pop();
			ans[p].pb(y);
			PQ.push(p);
		}
    }
    for(auto& tmp:ans){
		printf("%d ", int(tmp.size()));
		for(int x:tmp) printf("%d ", x);
		putchar(10);
	}
    return 0;
}

Compilation message

tea.cpp: In function 'void read(int&)':
tea.cpp:5:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 61312 KB Output is correct
2 Correct 46 ms 61352 KB Output is correct
3 Correct 44 ms 61304 KB Output is correct
4 Correct 38 ms 61304 KB Output is correct
5 Correct 38 ms 61304 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 61304 KB Output is correct
2 Correct 38 ms 61304 KB Output is correct
3 Correct 42 ms 61308 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 63936 KB Output is correct
2 Correct 104 ms 63352 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 63940 KB Output is correct
2 Correct 97 ms 63428 KB Output is correct
3 Correct 107 ms 63812 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 768 ms 81884 KB Output is correct
2 Correct 670 ms 81492 KB Output is correct
3 Correct 649 ms 83264 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 898 ms 90348 KB Output is correct
2 Correct 839 ms 147844 KB Output is correct
3 Correct 862 ms 87476 KB Output is correct
4 Correct 923 ms 86532 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 621 ms 92820 KB Output is correct
2 Correct 470 ms 92048 KB Output is correct
3 Correct 937 ms 87844 KB Output is correct
4 Correct 941 ms 90488 KB Output is correct