oj.uz

Submission #91971

# Submission time Handle Problem Language Result Execution time Memory
91971 2018-12-31T17:29:02 Z emil_physmath Gift (IZhO18_nicegift) C++17
37 / 100
 292 ms 30076 KB 
#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<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";
}

Compilation message

nicegift.cpp: In function 'void SubTaskTwo(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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 376 KB n=3
3 Correct 2 ms 376 KB n=3
4 Correct 2 ms 376 KB n=4
5 Correct 2 ms 248 KB n=4
6 Correct 2 ms 376 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 376 KB n=3
3 Correct 2 ms 376 KB n=3
4 Correct 2 ms 376 KB n=4
5 Correct 2 ms 248 KB n=4
6 Correct 2 ms 376 KB n=2
7 Correct 2 ms 376 KB n=5
8 Correct 6 ms 1016 KB n=8
9 Correct 10 ms 1204 KB n=14
10 Correct 7 ms 1016 KB n=11
11 Correct 54 ms 6316 KB n=50000
12 Correct 57 ms 6700 KB n=50000
13 Correct 33 ms 3496 KB n=10
14 Correct 32 ms 3252 KB n=685
15 Correct 35 ms 3368 KB n=623
16 Correct 20 ms 2096 KB n=973

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 376 KB n=3
3 Correct 2 ms 376 KB n=3
4 Correct 2 ms 376 KB n=4
5 Correct 2 ms 248 KB n=4
6 Correct 2 ms 376 KB n=2
7 Correct 2 ms 376 KB n=5
8 Correct 6 ms 1016 KB n=8
9 Correct 10 ms 1204 KB n=14
10 Correct 7 ms 1016 KB n=11
11 Correct 54 ms 6316 KB n=50000
12 Correct 57 ms 6700 KB n=50000
13 Correct 33 ms 3496 KB n=10
14 Correct 32 ms 3252 KB n=685
15 Correct 35 ms 3368 KB n=623
16 Correct 20 ms 2096 KB n=973
17 Incorrect 2 ms 256 KB Unexpected end of file - int32 expected
18 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 30076 KB n=1000000
2 Correct 178 ms 18552 KB n=666666
3 Correct 105 ms 10488 KB n=400000
4 Correct 236 ms 21624 KB n=285714
5 Correct 6 ms 784 KB n=20000
6 Correct 211 ms 18140 KB n=181818
7 Correct 4 ms 504 KB n=10000
8 Correct 28 ms 2040 KB n=6666
9 Correct 3 ms 376 KB n=4000
10 Correct 150 ms 9484 KB n=2857
11 Correct 2 ms 376 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 376 KB n=3
3 Correct 2 ms 376 KB n=3
4 Correct 2 ms 376 KB n=4
5 Correct 2 ms 248 KB n=4
6 Correct 2 ms 376 KB n=2
7 Correct 2 ms 376 KB n=5
8 Correct 6 ms 1016 KB n=8
9 Correct 10 ms 1204 KB n=14
10 Correct 7 ms 1016 KB n=11
11 Correct 54 ms 6316 KB n=50000
12 Correct 57 ms 6700 KB n=50000
13 Correct 33 ms 3496 KB n=10
14 Correct 32 ms 3252 KB n=685
15 Correct 35 ms 3368 KB n=623
16 Correct 20 ms 2096 KB n=973
17 Incorrect 2 ms 256 KB Unexpected end of file - int32 expected
18 Halted 0 ms 0 KB -