Submission #418559

#TimeUsernameProblemLanguageResultExecution timeMemory
418559fvogel499Secret (JOI14_secret)C++14
100 / 100
528 ms8296 KiB
/* File created on 06/05/2021 at 15:10:35. Link to problem: Description: Time complexity: O() Space complexity: O() Status: DEV Copyright: Ⓒ 2021 Francois Vogel */ #include <iostream> #include <cmath> #include <vector> #include <bitset> #include <queue> #include <cstring> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <algorithm> using namespace std; #define pii pair<int, int> #define f first #define s second #define pb push_back #define ins insert #define cls clear #define ll long long const int siz = 1000; int b [siz][siz]; int a [siz]; int n; #include <secret.h> // int Secret(int x, int y) { // return x+2*(y/2); // } void bs(int start, int end) { if (start > end) return; int mid = (start+end)/2; b[mid][mid] = a[mid]; for (int i = mid-1; i >= start; i--) { b[i][mid] = Secret(a[i], b[i+1][mid]); } if (start >= end) return; b[mid+1][mid+1] = a[mid+1]; for (int i = mid+2; i <= end; i++) { b[mid+1][i] = Secret(b[mid+1][i-1], a[i]); } bs(start, mid-1); bs(mid+1, end); } void Init(int ln, int la []) { n = ln; for (int i = 0; i < n; i++) { a[i] = la[i]; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { b[i][j] = -1; } } bs(0, n-1); } int Query(int queryLeft, int queryRight) { if (queryLeft == queryRight) { return a[queryLeft]; } int start = 0; int end = n-1; while (true) { int mid = (start+end)/2; if (queryLeft <= mid and mid < queryRight) { int res = Secret(b[queryLeft][mid], b[mid+1][queryRight]); return res; } else if (queryLeft <= mid and mid == queryRight) { int res = b[queryLeft][mid]; return res; } if (queryRight <= mid) end = mid-1; else start = mid+1; } } // signed main() { // int ln = 10; // int la [ln] = {2, 5, 6, 7, 10, 5, 7, 10, 22, 100}; // Init(ln, la); // for (int i = 0; i < ln; i++) { // for (int j = i+1; j < ln; j++) { // int res = a[i]; // for (int k = i+1; k <= j; k++) res = Secret(res, a[k]); // // cout << " RUNNING: " << i << " " << j << endl; // int ans = Query(i, j); // if (res != ans) { // cout << "WA: " << i << " " << j << " ------> " << ans << " instead of " << res << endl; // } // } // } // int d = 0; // d++; // }
#Verdict Execution timeMemoryGrader output
Fetching results...