oj.uz

답안 #270561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
270561 2020-08-17T18:28:23 Z eohomegrownapps Restore Array (RMI19_restore) C++14
7 / 100
 147 ms 98296 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 98296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 98296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 147 ms 98296 KB Output isn't correct
12 Halted 0 ms 0 KB -