Submission #307098

#TimeUsernameProblemLanguageResultExecution timeMemory
307098syyXylophone (JOI18_xylophone)C++17
0 / 100
1 ms388 KiB
#include "xylophone.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++) #define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--) typedef pair<int, int> pi; typedef pair<pi, int> pii; typedef pair<pi, pi> pipi; #define f first #define s second typedef vector<int> vi; typedef vector<pi> vpi; typedef vector<pii> vpii; #define pb push_back #define pf push_front #define all(v) v.begin(), v.end() #define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin()); #define INF (int) 1e9 + 100 #define LLINF (ll) 1e18 #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge"))) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss int n, arr[5005], adj[5005], tri[5005]; void solve(int N) { n = N; FOR(i, 1, n-1) adj[i] = query(i, i+1); FOR(i, 1, n-2) tri[i] = query(i, i+2); arr[1] = 1, arr[2] = 1 + adj[1]; FOR(i, 1, n-2) { if (tri[i] == adj[i] + adj[i+1]) { if (arr[i+1] > arr[i]) arr[i+2] = arr[i] - tri[i]; else arr[i+2] = arr[i] + tri[i]; } else { if (arr[i+1] > arr[i]) arr[i+2] = arr[i+1] - adj[i+1]; else arr[i+2] = arr[i+1] + adj[i+1]; } } pi s = pi(INF, 0), b = pi(0, 0); FOR(i, 1, n) s = min(s, pi(arr[i], i)), b = max(b, pi(arr[i], i)); if (s.s > b.s) { arr[1] = 1, arr[2] = 1 - adj[1]; FOR(i, 1, n-2) { if (tri[i] == adj[i] + adj[i+1]) { if (arr[i+1] > arr[i]) arr[i+2] = arr[i] - tri[i]; else arr[i+2] = arr[i] + tri[i]; } else { if (arr[i+1] > arr[i]) arr[i+2] = arr[i+1] - adj[i+1]; else arr[i+2] = arr[i+1] + adj[i+1]; } } s = pi(INF, 0), b = pi(0, 0); FOR(i, 1, n) s = min(s, pi(arr[i], i)), b = max(b, pi(arr[i], i)); } FOR(i, 1, n) answer(i, arr[i] + n-b.f); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...