oj.uz

Submission #306401

# Submission time Handle Problem Language Result Execution time Memory
306401 2020-09-25T11:58:54 Z colazcy Hokej (COCI17_hokej) C++17
120 / 120
 249 ms 41976 KB 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5e5 + 100;
typedef long long ll;
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;
}
struct node{
	int v,tim,id;
	bool operator < (const node &rhs)const{
		if(v != rhs.v)return v > rhs.v;
		return tim > rhs.tim;
	}
}val[maxn];
struct seg{
	int l,r,v,d;
}ans[maxn];
int m,n,tot;
ll out;
vector<int> vec[maxn];
struct mpair{int x,y,z;};
vector<mpair> tmp;
int main(){
	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);
	ll sum = 0;
	for(int i = 1;i <= n;i++){
		int beg = sum % m;
		seg sa = seg{beg + 1,beg + min(val[i].tim,m - beg),val[i].id,val[i].v};
		sum += sa.r - sa.l + 1;
		val[i].tim -= sa.r - sa.l + 1;  
		ans[++tot] = sa;
		if(sum == 6 * m)break;
		if(!val[i].tim)continue;
		seg sb = seg{1,min(val[i].tim,m),val[i].id,val[i].v};
		if(sb.r >= beg)ans[tot] = seg{1,m,val[i].id,val[i].v},sum += beg;
		else ans[++tot] = sb,sum += sb.r - sb.l + 1;
		if(sum == 6 * m)break;
	}
	for(int i = 1;i <= tot;i++)
		for(int k = ans[i].l;k <= ans[i].r;k++)vec[k].push_back(ans[i].v);
	for(int i = 1;i <= m;i++)
		if(vec[i].size() > 6)return -1;
	for(int i = 1;i <= tot;i++)out += ll(ans[i].r - ans[i].l + 1) * ans[i].d;
	printf("%lld\n",out);
	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()){
						tmp.push_back(mpair{i - 1,vec[i - 1][j],vec[i][k]});
						vis[k] = 1;
						break;
					}
			}
		}		
	}
	printf("%d\n",(int)tmp.size());
	for(unsigned int i = 0;i < tmp.size();i++){
		printf("%d %d %d\n",tmp[i].x,tmp[i].y,tmp[i].z);
	}
	return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 10 ms 12288 KB Output is correct
3 Correct 131 ms 35856 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 58 ms 21624 KB Output is correct
6 Correct 10 ms 12288 KB Output is correct
7 Correct 10 ms 12288 KB Output is correct
8 Correct 43 ms 15992 KB Output is correct
9 Correct 244 ms 41832 KB Output is correct
10 Correct 249 ms 41976 KB Output is correct