oj.uz

Submission #329082

# Submission time Handle Problem Language Result Execution time Memory
329082 2020-11-19T00:33:56 Z monus1042 Kocka (COCI18_kocka) C++17
70 / 70
 123 ms 17772 KB 
// NK
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set;

void solve(){
	int n; cin >> n;
	vi l(n+2, -2), r(n+2, -2), u(n+2, -2);

	vector<set<int>> column(n+2); // co, ro
	//vector<set<int>> row(n+2); // r, co
	
	for (int i=1; i<=n; ++i){
		int x; cin >> x;
		l[i] = x;
		column[x+1].insert(i);
		//row[i].insert(x+1);
	}
	for (int i=1; i<=n; ++i){
		int x; cin >> x;
		if (l[i] == -1){
			if (x == -1){
				r[i] = -1;
			}else{
				cout << "NE\n";
				return;
			}
		}else{
			int cond = n-l[i]-1;
			if (0 <= x && x <= cond){
				r[i] = x;
				column[n-x].insert(i);
				//row[i].insert(n-x);
			}else{
				cout << "NE\n";
				return;
			}
		}
	}
	for (int i=1; i<=n; ++i){
		int x; cin >> x;
		if (x == -1){
			if (column[i].empty()){
				u[i] = x;
			}else{
				cout<<"NE\n";
				return;
			}
		}else{
			if (column[i].empty()){
				if (l[x+1] != -1 && l[x+1]+1 < i && i < n - r[x+1]){
					u[i] = x;
				}else{
					cout << "NE\n";
					return;
				}
			}else{
				auto beg = column[i].begin();
				int nearest = *beg;
				if (nearest < x + 1){
					cout << "NE\n";
					return;
				}else if(nearest == x + 1){
					
				}else if(x+1 < nearest){
					if (l[x+1] != -1 && l[x+1]+1 < i && i < n - r[x+1]){
						u[i] = x;
					}else{
						cout << "NE\n";
						return;
					}
				}
			}
		}
	}

	for (int i=1; i<=n; ++i){
		int x; cin >> x;
		if (u[i] == -1){
			if (x == -1){
				//ok
			}else{
				cout << "NE\n";
				return;
			}
		}else{
			int cond = n-u[i]-1;
			if (0 <= x && x <= cond){
				//ok
			}else{
				cout << "NE\n";
				return;
			}
		}

		/////
		int cor = n-x;
		if (x == -1){
			if (column[i].empty()){
				//ok
			}else{
				cout<<"NE\n";
				return;
			}
		}else{
			if (column[i].empty()){
				if (l[cor] != -1 && l[cor]+1 < i && i < n - r[cor]){
					//ok
				}else{
					cout << "NE\n";
					return;
				}
			}else{
				auto beg = column[i].end();
				beg--;
				int nearest = *beg;
				if (nearest > cor){
					cout << "NE\n";
					return;
				}else if(nearest == cor){
					
				}else if(cor > nearest){
					if (l[cor] != -1 && l[cor]+1 < i && i < n - r[cor]){
						
					}else{
						cout << "NE\n";
						return;
					}
				}
			}
		}
	}
	cout << "DA\n";
}

int main(){
	Bolivia_is_nice;
	int t = 1; //cin>>t;
	while(t--)
	solve();
	
	return 0;
}
/*
  ~/.emacs
*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14060 KB Output is correct
2 Correct 43 ms 11628 KB Output is correct
3 Correct 41 ms 11628 KB Output is correct
4 Correct 53 ms 12140 KB Output is correct
5 Correct 45 ms 11776 KB Output is correct
6 Correct 46 ms 11884 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17644 KB Output is correct
2 Correct 49 ms 12140 KB Output is correct
3 Correct 42 ms 11628 KB Output is correct
4 Correct 103 ms 16876 KB Output is correct
5 Correct 38 ms 11776 KB Output is correct
6 Correct 118 ms 17772 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 14060 KB Output is correct
2 Correct 52 ms 12140 KB Output is correct
3 Correct 47 ms 11756 KB Output is correct
4 Correct 43 ms 11628 KB Output is correct
5 Correct 40 ms 11756 KB Output is correct
6 Correct 50 ms 12140 KB Output is correct