oj.uz

Submission #91972

# Submission time Handle Problem Language Result Execution time Memory
91972 2018-12-31T17:30:32 Z emil_physmath Gift (IZhO18_nicegift) C++17
49 / 100
 2000 ms 210740 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 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";
}

Compilation message

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.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 256 KB n=4
5 Correct 2 ms 376 KB n=4
6 Correct 2 ms 256 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 256 KB n=4
5 Correct 2 ms 376 KB n=4
6 Correct 2 ms 256 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 53 ms 6444 KB n=50000
12 Correct 53 ms 6700 KB n=50000
13 Correct 34 ms 3500 KB n=10
14 Correct 30 ms 3116 KB n=685
15 Correct 33 ms 3520 KB n=623
16 Correct 19 ms 2092 KB n=973

Subtask #3
12.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 256 KB n=4
5 Correct 2 ms 376 KB n=4
6 Correct 2 ms 256 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 53 ms 6444 KB n=50000
12 Correct 53 ms 6700 KB n=50000
13 Correct 34 ms 3500 KB n=10
14 Correct 30 ms 3116 KB n=685
15 Correct 33 ms 3520 KB n=623
16 Correct 19 ms 2092 KB n=973
17 Correct 33 ms 2608 KB n=989
18 Correct 15 ms 1272 KB n=563
19 Correct 24 ms 1784 KB n=592
20 Correct 25 ms 1784 KB n=938
21 Correct 19 ms 1528 KB n=747
22 Correct 22 ms 1520 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 30092 KB n=1000000
2 Correct 187 ms 18424 KB n=666666
3 Correct 106 ms 10488 KB n=400000
4 Correct 242 ms 21624 KB n=285714
5 Correct 6 ms 760 KB n=20000
6 Correct 221 ms 18168 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 153 ms 9464 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 256 KB n=4
5 Correct 2 ms 376 KB n=4
6 Correct 2 ms 256 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 53 ms 6444 KB n=50000
12 Correct 53 ms 6700 KB n=50000
13 Correct 34 ms 3500 KB n=10
14 Correct 30 ms 3116 KB n=685
15 Correct 33 ms 3520 KB n=623
16 Correct 19 ms 2092 KB n=973
17 Correct 33 ms 2608 KB n=989
18 Correct 15 ms 1272 KB n=563
19 Correct 24 ms 1784 KB n=592
20 Correct 25 ms 1784 KB n=938
21 Correct 19 ms 1528 KB n=747
22 Correct 22 ms 1520 KB n=991
23 Correct 301 ms 30092 KB n=1000000
24 Correct 187 ms 18424 KB n=666666
25 Correct 106 ms 10488 KB n=400000
26 Correct 242 ms 21624 KB n=285714
27 Correct 6 ms 760 KB n=20000
28 Correct 221 ms 18168 KB n=181818
29 Correct 4 ms 504 KB n=10000
30 Correct 28 ms 2040 KB n=6666
31 Correct 3 ms 376 KB n=4000
32 Correct 153 ms 9464 KB n=2857
33 Correct 2 ms 376 KB n=2000
34 Execution timed out 2068 ms 210740 KB Time limit exceeded
35 Halted 0 ms 0 KB -