Cod sursa(job #1448460)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 7 iunie 2015 09:36:26
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <vector>
#include <stack>
#include <numeric>
using namespace std;

int main(){
	ifstream f("harta.in");
	ofstream g("harta.out");
	int n;
	f >> n;
	vector<int> in_deg(n), out_deg(n);
	for(int i = 0; i < n; ++i){
		f >> out_deg[i] >> in_deg[i]; }
	g << accumulate(begin(in_deg), end(in_deg), 0) << '\n';
	vector<stack<int> > stive(n);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < i; ++j){
			stive[in_deg[j]].push(j); }
		for(int j = i+1; j < n; ++j){
			stive[in_deg[j]].push(j); }
		for(auto it = stive.rbegin(); out_deg[i] && it != stive.rend(); ++it){
			while(out_deg[i] && !(it->empty())){
				g << (i+1) << ' ' << (it->top()+1) << '\n';
				--out_deg[i];
				--in_deg[it->top()];
				it->pop(); } }
		for(auto& st : stive){
			st = stack<int>(); } }
	return 0; }