Submission #341688

#	Time	Username	Problem	Language	Result	Execution time	Memory
341688		maskoff	Gift (IZhO18_nicegift)	C++14	49 / 100	1868 ms	23916 KiB

nicegift

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define right lol
#define left loool

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 1e6 + 5;
           
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};  

int b[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

ll n, k;
ll a[N];
ll sum, pos = -1;

void solve2() {
	vector<vector<int>> ans;
	set<pii> s;
	for (int i = 1; i <= n; i++)
 		s.insert({-a[i], i});
 	while (!s.empty()) {
 		if (s.size() < k) cout << -1, exit(0);
 		int cnt = k;
 		vector<int> cur;
 		vector<pii> build;
 		while (cnt--) {
 			pii x = {s.begin() -> fr, s.begin() -> sc};
 			s.erase(s.begin());
 			cur.pb(x.sc);
 			build.pb({x.fr + 1, x.sc});
 		}
 		for (auto t : build) if (t.fr != 0) s.insert({t.fr, t.sc});
 		ans.pb(cur);
  }		
  cout << ans.size() << endl;
  for (auto t : ans) {
   	cout << 1 << " ";
   	for (int p : t) cout << p << " ";
   	cout << "\n";
  }
  exit(0);
}

void solve3() {
	ll p = n * k / __gcd(n, k);
	ll time_n = p / n;
	ll time_k = p / k;
	if (a[1] % time_n != 0) cout << -1, exit(0);
	ll x = a[1] / time_n;
	int last = 1;
	//if (time_k * 1ll * k >= (int) 3e6) cout << -1, exit(0);
	cout << time_k << endl;
	for (int i = 1; i <= time_k; i++) {
	 	cout << x << " ";
	 	int cnt = k;
	 	while (cnt--) {
	 		cout << last << " ";
	 		last++;
	 		if (last == n + 1) last = 1;
	 	}
	 	cout << endl;               
	}
}

int main() { 
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; 	
		sum += a[i];
	}
	if (sum <= 1e5) solve2();
	else solve3();
  return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'void solve2()':
nicegift.cpp:41:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   41 |    if (s.size() < k) cout << -1, exit(0);
      |        ~~~~~~~~~^~~

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