oj.uz

Submission #341688

# Submission time Handle Problem Language Result Execution time Memory
341688 2020-12-30T12:20:43 Z maskoff Gift (IZhO18_nicegift) C++14
49 / 100
 1868 ms 23916 KB 
#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

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.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 3 ms 1004 KB n=8
9 Correct 11 ms 1192 KB n=14
10 Correct 6 ms 1004 KB n=11
11 Correct 54 ms 5664 KB n=50000
12 Correct 57 ms 5920 KB n=50000
13 Correct 36 ms 3504 KB n=10
14 Correct 37 ms 3232 KB n=685
15 Correct 41 ms 3380 KB n=623
16 Correct 23 ms 2084 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 3 ms 1004 KB n=8
9 Correct 11 ms 1192 KB n=14
10 Correct 6 ms 1004 KB n=11
11 Correct 54 ms 5664 KB n=50000
12 Correct 57 ms 5920 KB n=50000
13 Correct 36 ms 3504 KB n=10
14 Correct 37 ms 3232 KB n=685
15 Correct 41 ms 3380 KB n=623
16 Correct 23 ms 2084 KB n=973
17 Correct 38 ms 2596 KB n=989
18 Correct 16 ms 1004 KB n=563
19 Correct 27 ms 1388 KB n=592
20 Correct 28 ms 1516 KB n=938
21 Correct 21 ms 1132 KB n=747
22 Correct 25 ms 1388 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1868 ms 22984 KB n=1000000
2 Correct 959 ms 22892 KB n=666666
3 Correct 460 ms 12868 KB n=400000
4 Correct 1084 ms 23916 KB n=285714
5 Correct 20 ms 876 KB n=20000
6 Correct 772 ms 19680 KB n=181818
7 Correct 8 ms 620 KB n=10000
8 Correct 48 ms 2156 KB n=6666
9 Correct 4 ms 492 KB n=4000
10 Correct 256 ms 9708 KB n=2857
11 Correct 2 ms 364 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 3 ms 1004 KB n=8
9 Correct 11 ms 1192 KB n=14
10 Correct 6 ms 1004 KB n=11
11 Correct 54 ms 5664 KB n=50000
12 Correct 57 ms 5920 KB n=50000
13 Correct 36 ms 3504 KB n=10
14 Correct 37 ms 3232 KB n=685
15 Correct 41 ms 3380 KB n=623
16 Correct 23 ms 2084 KB n=973
17 Correct 38 ms 2596 KB n=989
18 Correct 16 ms 1004 KB n=563
19 Correct 27 ms 1388 KB n=592
20 Correct 28 ms 1516 KB n=938
21 Correct 21 ms 1132 KB n=747
22 Correct 25 ms 1388 KB n=991
23 Correct 1868 ms 22984 KB n=1000000
24 Correct 959 ms 22892 KB n=666666
25 Correct 460 ms 12868 KB n=400000
26 Correct 1084 ms 23916 KB n=285714
27 Correct 20 ms 876 KB n=20000
28 Correct 772 ms 19680 KB n=181818
29 Correct 8 ms 620 KB n=10000
30 Correct 48 ms 2156 KB n=6666
31 Correct 4 ms 492 KB n=4000
32 Correct 256 ms 9708 KB n=2857
33 Correct 2 ms 364 KB n=2000
34 Incorrect 41 ms 804 KB Taken too much stones from the heap
35 Halted 0 ms 0 KB -