oj.uz

Submission #640909

# Submission time Handle Problem Language Result Execution time Memory
640909 2022-09-15T14:09:35 Z andreast12 Kocka (COCI18_kocka) C++17
70 / 70
 44 ms 5756 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int mod=998244353, maxn=1e5+5;
int n, a[10][maxn], ki, ka, atas, bwh, kolmin[maxn], kolmax[maxn];
bool ans=true;
pair<int, int> baris[maxn];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i=1; i<=4; i++) {
		for(int j=1; j<=n; j++) cin >> a[i][j];
	}
	for(int i=0; i<=n; i++) kolmin[i]=mod, kolmax[i]=-1;
	for(int i=1; i<=n; i++) {
		if(((a[1][i]==-1)^(a[2][i]==-1))||a[1][i]+a[2][i]+1>n) ans=false;
		if(a[1][i]==-1&&a[2][i]==-1) {
			baris[i]={-1, -1};
		} else {
			ki=a[1][i]+1, ka=n-a[2][i];
			baris[i]={ki, ka};
			kolmin[ki]=min(kolmin[ki], i);
			kolmax[ki]=max(kolmax[ki], i);
			kolmin[ka]=min(kolmin[ka], i);
			kolmax[ka]=max(kolmax[ka], i);
		}
	} 
	// for(int i=1; i<=n; i++) cout << i << ": " << kolmin[i] << ' ' << kolmax[i] << '\n';
	for(int i=1; i<=n; i++) {
		if(((a[3][i]==-1)^(a[4][i]==-1))||a[3][i]+a[4][i]+1>n) ans=false;
		if(a[3][i]==-1&&a[4][i]==-1) {
			if(kolmin[i]!=mod||kolmax[i]!=-1) ans=false;
		} else {
			// if(i==1) cout << "YYY\n";
			atas=a[3][i]+1, bwh=n-a[4][i];
			if(atas>kolmin[i]||bwh<kolmax[i]) ans=false;
			else {
				if(baris[atas]==make_pair(-1, -1)||baris[bwh]==make_pair(-1, -1)) ans=false;
				else {
					if(i<baris[atas].fi||i>baris[atas].se||i<baris[bwh].fi||i>baris[bwh].se) ans=false;
				}
			}
		}
	}
	cout << ((ans)?"DA":"NE") << '\n';
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5220 KB Output is correct
2 Correct 32 ms 5692 KB Output is correct
3 Correct 44 ms 5640 KB Output is correct
4 Correct 22 ms 4568 KB Output is correct
5 Correct 33 ms 5740 KB Output is correct
6 Correct 32 ms 5756 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5208 KB Output is correct
2 Correct 28 ms 4516 KB Output is correct
3 Correct 33 ms 5752 KB Output is correct
4 Correct 32 ms 4668 KB Output is correct
5 Correct 35 ms 5740 KB Output is correct
6 Correct 31 ms 5488 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5164 KB Output is correct
2 Correct 25 ms 4512 KB Output is correct
3 Correct 31 ms 5688 KB Output is correct
4 Correct 32 ms 5676 KB Output is correct
5 Correct 31 ms 5708 KB Output is correct
6 Correct 22 ms 4552 KB Output is correct