Submission #314676

#TimeUsernameProblemLanguageResultExecution timeMemory
314676mohamedsobhi777Kocka (COCI18_kocka)C++14
14 / 70
117 ms19328 KiB
#include <bits/stdc++.h> #pragma GCC optimize("-Ofast") //#pragma GCC optimize("trapv") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-funroll-loops") #define I inline void #define S struct #define vi vector<int> #define vii vector<pair<int, int>> #define pii pair<int, int> #define pll pair<ll, ll> using namespace std; using ll = long long; using ld = long double; const int N = 2e5 + 7, mod = 1e9 + 7; const ll inf = 2e18; // How interesting! int n; int d[4][N]; vector<int> vec[N], hrn[N]; void no() { cout << "NE"; exit(0); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("in.in", "r", stdin); cin >> n; for (int i = 0; i < 4; ++i) { for (int j = 0; j < n; ++j) { cin >> d[i][j]; } } for (int i = 0; i < n; ++i) { int a = d[0][i], b = d[1][i]; if (min(a, b) == -1 && max(a, b) > -1) no(); if (a + b >= n) no(); if (a == -1) continue; vec[a].push_back(i); hrn[i].push_back(a); if (a != n - 1 - b) { hrn[i].push_back(n - 1 - b); vec[n - 1 - b].push_back(i); } } for (int i = 0; i < n; ++i) { int a = d[2][i], b = d[3][i]; if (min(a, b) == -1 && max(a, b) > -1) no(); if (a + b >= n) no(); if (a == -1) continue; hrn[a].push_back(i); vec[i].push_back(a); if (a != n - 1 - b) { hrn[n - 1 - b].push_back(i); vec[i].push_back(n - 1 - b); } } for (int i = 0; i < n; ++i) { if (d[0][i] == -1 && hrn[i].size()) no(); if (d[0][i] == -1) continue; int A = hrn[i][0]; int B = n - hrn[i].back() - 1; if (d[0][i] != A || d[1][i] != B) no(); } for (int i = 0; i < n; ++i) { if (d[2][i] == -1 && vec[i].size()) no(); if (d[2][i] == -1) continue; int A = vec[i][0]; int B = n - vec[i].back() - 1; if (d[2][i] != A || d[3][i] != B) no(); } cout << "DA"; return 0; } /* - bounds sir (segtree = 4N, eulerTour = 2N, ...) - a variable defined twice? - will overflow? - is it a good complexity? - don't mess up indices (0-indexed vs 1-indexed) - reset everything between testcases. */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...