oj.uz

Submission #378862

# Submission time Handle Problem Language Result Execution time Memory
378862 2021-03-17T06:36:14 Z Seanliu Gift (IZhO18_nicegift) C++17
0 / 100
 189 ms 125196 KB 
#include <iostream>
#include <map>
#include <deque>
#include <vector>
#define int long long int
using namespace std;

const int maxN = 1e5 + 326;
map<int, deque<int>> mp;
vector<vector<int>> ans;

int N, K, arr[maxN];
int sm[maxN];

struct Obj{
	int num;
	deque<int> poss;
	Obj(){}
	Obj(int num, deque<int> dq): num(num), poss(dq){}
};

deque<Obj> has[maxN];

signed main(){
	cin >> N >> K;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
		if(!mp.count(arr[i])){
			mp[arr[i]] = deque<int>();
		}
		mp[arr[i]].push_back(i);
	}
	for(auto &[v, vec] : mp){
		while(vec.size() >= K){
			vector<int> tmp = vector<int>();
			tmp.push_back(v);
			for(int i = 0; i < K; i++){
				tmp.push_back(vec.front());
				vec.pop_front();
			}
			ans.push_back(tmp);
		}
		if(vec.size()){
			has[vec.size()].emplace_back(v, vec);
			sm[vec.size()] += v;
		}
	}
	for(int i = 1; i < K && i <= (K - i); i++){
		if(sm[i] != sm[K - i]){
			cout << -1 << endl;
			return 0;
		}
		while(has[i].size()){
			if(2 * i == K){
				if(has[i].size() == 1){
					cout << -1 << endl;
					return 0;
				}
				Obj o1 = has[i].front(); has[i].pop_front(); 
				Obj o2 = has[i].front(); has[i].pop_front(); 
				vector<int> tmp = vector<int>();
				tmp.push_back(min(o1.num, o2.num));
				for(int x : o1.poss) tmp.push_back(x);
				for(int x : o2.poss) tmp.push_back(x);
				if(tmp[0] != o1.num){
					o1.num -= tmp[0];
					has[i].push_front(o1);
				}
				if(tmp[0] != o2.num){
					o2.num -= tmp[0];
					has[i].push_front(o2);
				}
			} else {
				vector<int> tmp = vector<int>();
				tmp.push_back(min(has[i].front().num, has[K - i].front().num));
				for(int x : has[i].front().poss) tmp.push_back(x);
				for(int x : has[K - i].front().poss) tmp.push_back(x);
				ans.push_back(tmp);
				if(tmp[0] == has[i].front().num) has[i].pop_front();
				else {
					has[i][0].num -= tmp[0];
				}
				if(tmp[0] == has[K - i].front().num) has[K - i].pop_front();
				else {
					has[K - i][0].num -= tmp[0];
				}
			}
		}
	}
	cout << ans.size() << endl;
	for(auto v : ans){
		for(int x : v) cout << x << " ";
		cout << endl;
	}
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:34:20: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |   while(vec.size() >= K){
      |         ~~~~~~~~~~~^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 60012 KB n=4
2 Incorrect 50 ms 60012 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 60012 KB n=4
2 Incorrect 50 ms 60012 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 60012 KB n=4
2 Incorrect 50 ms 60012 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 125196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 60012 KB n=4
2 Incorrect 50 ms 60012 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -