제출 #91970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91970		emil_physmath	Gift (IZhO18_nicegift)	C++17	37 / 100	303 ms	30184 KiB

nicegift

#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
const long long MAXN=1000005;

long long a[MAXN], ansL[MAXN];

void SubTaskFour(long long n, long long k, long long h);
void SubTaskTwo(long long n, long long k);
int main()
{
	long long n, k;
	cin>>n>>k;
	for (int i=0; i<n; i++)
		scanf("%lld", a+i);
	bool isSubTaskFour=true;
	for (int i=1; i<n; i++)
		if (a[i]!=a[0])
		{
			isSubTaskFour=false;
			break;
		}
	if (isSubTaskFour)
		SubTaskFour(n, k, a[0]);
	else if (k==2)
		SubTaskTwo(n, k);

	char I;
	cin >> I;
	return 0;
}

void SubTaskFour(long long n, long long k, long long h)
{
	if ((n*h)%k)
	{
		cout<<"-1\n";
		return;
	}
	long long l=1, r=k, l_i=1, r_i=1;
	long long numRep=1;
	while (r_i<=h)
	{
		if (l==1 && l_i!=1)
		{
			numRep=h/(l_i-1);
			break;
		}
		ansL[l]++;
		l=r+1;
		l_i=r_i;
		if (l>n)
		{
			l%=n;
			l_i++;
		}
		if (l+k-1<=n)
		{
			r=l+k-1;
			r_i=l_i;
		}
		else
		{
			r=(l+k-1)%n;
			r_i=l_i+1;
		}
	}
	long long op=0;
	for (long long curL=1; curL<=n; curL++)
		if (ansL[curL])
			op++;
	cout<<op<<'\n';
	for (long long curL=1; curL<=n; curL++)
	{
		if (!ansL[curL]) continue;
		long long tempK=k, i=curL;
		printf("%lld ", numRep*ansL[curL]);
		while (tempK--)
		{
			printf("%lld ", i);
			i++;
			if (i>n) i%=n;
		}
		printf("\n");
	}
}

void SubTaskTwo(long long n, long long k)
{
	set<pair<long long, long long> > col;
	vector<pair<long long, long long> > ans;
	for (int i=0; i<n; i++)
		col.insert(make_pair(a[i], i+1));
	while (!col.empty())
	{
		while (!col.empty() && !col.begin()->first)
			col.erase(col.begin());
		if (col.empty())
			break;
		if (col.size()>=2)
		{
			set<pair<long long, long long> >::reverse_iterator
				it[2]={col.rbegin(), ++col.rbegin()};
			ans.push_back(make_pair(it[0]->second, it[1]->second));
			long long ind[2], hei[2];
			for (int i=0; i<=1; i++)
				ind[i]=it[i]->second, hei[i]=it[i]->first;
			for (int i=0; i<=1; i++)
			{
				col.erase(col.find(make_pair(hei[i], ind[i])));
				hei[i]--;
				col.insert(make_pair(hei[i], ind[i]));
			}
		}
		else
			break;
	}
	if (col.empty())
	{
		cout<<ans.size()<<'\n';
		for (int i=0; i<ans.size(); i++)
			printf("1 %lld %lld\n", ans[i].first, ans[i].second);
	}
	else
		cout<<"-1\n";
}

컴파일 시 표준 에러 (stderr) 메시지

nicegift.cpp: In function 'void SubTaskTwo(long long int, long long int)':
nicegift.cpp:123:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<ans.size(); i++)
                 ~^~~~~~~~~~~
nicegift.cpp: In function 'int main()':
nicegift.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a+i);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 51