Submission #272412

#	Time	Username	Problem	Language	Result	Execution time	Memory
272412		eohomegrownapps	Restore Array (RMI19_restore)	C++14	7 / 100	141 ms	98440 KiB

restore

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

int n,m;

void relaxedges(){
	int a[20001], b[20001], c[20001];
	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;
		}
	}
	for (int i = 0; i<n; i++){
		a[m+2*i]=i;
		b[m+2*i]=i+1;
		c[m+2*i]=-1;
		a[m+2*i+1]=i+1;
		b[m+2*i+1]=i;
		c[m+2*i+1]=0;
	}
	m+=2*n;
	bool changed = true;
	bool works = true;
	int minvals[20001], maxvals[20001];
	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 (minvals[b[i]]>maxvals[b[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));
	//assert(minvals[0]==0&&maxvals[0]==0);
	parent[0][0]=0;
	int ind = 0;
	for (int y = 1; y<=n; y++){
		bool works = false;
		for (int x = maxvals[y]; x>=minvals[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];
	}
	reverse(ans.begin(),ans.end());
	for (int i = 0; i<n; i++){
		cout<<ans[i]<<' ';
	}cout<<'\n';
	vector<int> s(n+1,0);
	for (int i = 1; i<=n; i++){
		s[i]=s[i-1]+ans[i-1];
		//cout<<minvals[i]<<' '<<maxvals[i]<<' '<<s[i]<<'\n';
		assert(minvals[i]<=s[i]&&s[i]<=maxvals[i]);
	}
	/*for (int i = 0; i<m; i++){
		assert(s[a[i]]>=s[b[i]]+c[i]);
	}*/
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	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