제출 #91972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91972		emil_physmath	Gift (IZhO18_nicegift)	C++17	49 / 100	2068 ms	210740 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 SubTaskThree(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
		SubTaskThree(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 SubTaskThree(long long n, long long k)
{
	set<pair<long long, long long> > col;
	vector<vector<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()>=k)
		{
			vector<long long> curAns;
			vector< set<pair<long long, long long> >::iterator > it(k);
			auto curRIt=--col.end();
			for (int i=0; i<k; i++, curRIt--)
				it[i]=curRIt;
			vector<long long> ind(k), hei(k);
			for (int i=0; i<k; i++)
				ind[i]=it[i]->second, hei[i]=it[i]->first;
			for (int i=0; i<k; i++)
			{
				col.erase(it[i]);
				hei[i]--;
				col.insert(make_pair(hei[i], ind[i]));
				curAns.push_back(ind[i]);
			}
			ans.push_back(curAns);
		}
		else
			break;
	}
	if (col.empty())
	{
		cout<<ans.size()<<'\n';
		for (int i=0; i<ans.size(); i++)
		{
			printf("1 ");
			for (int j=0; j<ans[i].size(); j++)
				printf("%lld ", ans[i][j]);
			printf("\n");
		}
	}
	else
		cout<<"-1\n";
}

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

nicegift.cpp: In function 'void SubTaskThree(long long int, long long int)':
nicegift.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (col.size()>=k)
       ~~~~~~~~~~^~~
nicegift.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<ans.size(); i++)
                 ~^~~~~~~~~~~
nicegift.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0; j<ans[i].size(); j++)
                  ~^~~~~~~~~~~~~~
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: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 51