제출 #378861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378861		Seanliu	Gift (IZhO18_nicegift)	C++14	0 / 100	317 ms	524292 KiB

nicegift

#include <iostream>
#include <map>
#include <deque>
#include <vector>
#define int long long int
using namespace std;

const int maxN = 1e6 + 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;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

nicegift.cpp: In function 'int main()':
nicegift.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |  for(auto &[v, vec] : mp){
      |            ^
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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 51