제출 #306393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306393		colazcy	Hokej (COCI17_hokej)	C++17	12 / 120	1097 ms	18352 KiB

hokej

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5e5 + 100;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
int m,n;
long long ans;
struct player{
	int v,tim,id;
	bool operator < (const player &rhs)const{
		if(v != rhs.v)return v > rhs.v;
		return tim > rhs.tim;
	}
}val[maxn];
vector<int> vec[maxn];
struct mpair{int x,y,z;};
vector<mpair> out;
int main(){
	//freopen("hokej.in.4","r",stdin);
//	freopen("hokej.out","w",stdout);
	m = read(),n = read();
	for(int i = 1;i <= n;i++)
		val[i].v = read(),val[i].tim = read(),val[i].id = i;
	sort(val + 1,val + 1 + n);
	int pos = 1;
	for(int i = 1;i <= n;i++){
		while(vec[pos].size() == 6)pos++;
		if(pos == m + 1)break;
		int tmp = pos;
		for(int j = pos;j <= m && val[i].tim;j++){
			if(vec[j].size() >= 6)continue;
			vec[j].push_back(val[i].id);
			ans += val[i].v;
			val[i].tim--;
			while(vec[pos].size() == 6)pos++;
			if(pos == m + 1)break;
			for(int p = tmp - 1;p >= 1 && val[i].tim;p--){
				for(unsigned int k = 0;k < 6;k++)
					if(find(vec[j].begin(),vec[j].end(),vec[p][k]) == vec[j].end()){
						if(vec[j].size() < 6){
							vec[j].push_back(vec[p][k]);
							vec[p][k] = val[i].id;
							ans += val[i].v;
							val[i].tim--;
							break;
						}
					}
			}
		}
	}
	printf("%lld\n",ans);
	for(unsigned int i = 0;i < 6;i++)printf("%d ",vec[1][i]);
	printf("\n");
	int vis[6];
	for(int i = 2;i <= m;i++){
		for(int j = 0;j < 6;j++)vis[j] = 0;
		for(unsigned int j = 0;j < 6;j++){
			int flag = 0;
			for(unsigned int k = 0;k < 6;k++)
				if(vec[i - 1][j] == vec[i][k]){
					flag = 1;
					break;
				}
			if(!flag){
				for(unsigned int k = 0;k < 6;k++)	
					if(vec[i - 1][j] != vec[i][k] && !vis[k] && find(vec[i - 1].begin(),vec[i - 1].end(),vec[i][k]) == vec[i - 1].end()){
						out.push_back(mpair{i - 1,vec[i - 1][j],vec[i][k]});
						vis[k] = 1;
						break;
					}
			}
		}		
	}
	printf("%d\n",(int)out.size());
	for(unsigned int i = 0;i < out.size();i++){
		printf("%d %d %d\n",out[i].x,out[i].y,out[i].z);
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

• Subtask 1: 12 / 120