Submission #640909

#	Time	Username	Problem	Language	Result	Execution time	Memory
640909		andreast12	Kocka (COCI18_kocka)	C++17	70 / 70	44 ms	5756 KiB

kocka

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14