제출 #270561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270561		eohomegrownapps	Restore Array (RMI19_restore)	C++14	7 / 100	147 ms	98296 KiB

restore

#include <bits/stdc++.h>
using namespace std;

int n,m;

void subtask1(){
	int l[200];
	int r[200];
	int k[200];
	int v[200];
	for (int i = 0; i<m; i++){
		cin>>l[i]>>r[i]>>k[i]>>v[i];
	}
	for (int i = 0; i<(1<<n); i++){
		//cout<<"check\n";
		bool works = true;
		for (int j = 0; j<m; j++){
			int cnt0 = 0;
			for (int x = l[j]; x<=r[j]; x++){
				if ((1<<x)&i){
					continue;
				} else {
					cnt0++;
				}
			}
			//cout<<l[j]<<' '<<r[j]<<' '<<cnt0<<'\n';
			if (!((v[j]&&cnt0<k[j])||((!v[j])&&cnt0>=k[j]))){
				works=false;
				break;
			}
		}
		if (works){
			for (int x = 0; x<n; x++){
				cout<<bool((1<<x)&i)<<' ';
			}cout<<'\n';
			return;
		}
	}
	cout<<-1<<'\n';
	return;
}

void relaxedges(){
	int a[10000], b[10000], c[10000];
	for (int i = 0; i<m; i++){
		int l,r,k,v;
		cin>>l>>r>>k>>v;
		r++;
		if (v==0){
			a[i]=l;
			b[i]=r;
			c[i]=k-(r-l);
		} else {
			a[i]=r;
			b[i]=l;
			c[i]=(r-l)-k+1;
		}
	}
	bool changed = true;
	bool works = true;
	int minvals[5001], maxvals[5001];
	for (int i = 0; i<=n; i++){
		minvals[i]=0;
		maxvals[i]=i;
	}
	while (changed&&works){
		changed=false;
		for (int i = 0; i<m; i++){
			if (minvals[b[i]]+c[i]>minvals[a[i]]){
				changed=true;
				minvals[a[i]]=minvals[b[i]]+c[i];
			}
			if (maxvals[a[i]]-c[i]<maxvals[b[i]]){
				changed=true;
				maxvals[b[i]]=maxvals[a[i]]-c[i];
			}
			if (minvals[a[i]]>maxvals[a[i]]){
				works=false;
			}
		}
	}
	if (!works){
		cout<<-1<<'\n';
		return;
	}
	/*for (int i = 0; i<=n; i++){
		cout<<minvals[i]<<' '<<maxvals[i]<<'\n';
	}*/
	vector<vector<int>> parent(n+1,vector<int>(n+1,-1));
	parent[0][0]=0;
	int ind = 0;
	for (int y = 1; y<=n; y++){
		bool works = false;
		for (int x = minvals[y]; x<=maxvals[y]; x++){
			if (x-1>=0){
				if (parent[y-1][x-1]!=-1){
					parent[y][x]=x-1;
					works=true;
					ind = x;
				}
			}
			if (parent[y-1][x]!=-1){
				parent[y][x]=x;
				works=true;
				ind = x;
			}
		}
		if (!works){
			cout<<-1<<'\n';
			return;
		}
	}
	/*for (int y = 0; y<=n; y++){
		for (int x = 0; x<=n; x++){
			cout<<parent[y][x]<<' ';
		}cout<<'\n';
	}*/
	vector<bool> ans;
	for (int i = n; i>0; i--){
		if (ind==parent[i][ind]){
			ans.push_back(0);
		} else {
			ans.push_back(1);
		}
		ind=parent[i][ind];
	}
	for (int i = n-1; i>=0; i--){
		cout<<ans[i]<<' ';
	}cout<<'\n';
}


int main(){
	cin>>n>>m;
	/*if (n<=18){
		subtask1();
	} else {*/
		relaxedges();
	//}
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55