제출 #262965

#제출 시각아이디문제언어결과실행 시간메모리
262965shayan_p코알라 (APIO17_koala)C++14
67 / 100
81 ms512 KiB
// And you curse yourself for things you never done #include<bits/stdc++.h> #include "koala.h" #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 110, mod = 1e9 + 7, inf = 1e9 + 10; int minValue(int N, int W) { int A[maxn], B[maxn]; memset(A, 0, sizeof A); memset(B, 0, sizeof B); A[0] = 1; playRound(A, B); if(B[0] <= 1) return 0; int ans = 0; for(int i = 1; i < N; i++) if(B[i] == 0) ans = i; return ans; } int maxValue(int N, int W) { int SM[maxn]; vector<pii> v[maxn]; int h[maxn]; pii pr[maxn]; memset(SM, 0, sizeof SM); memset(h, -1, sizeof h); for(int i = 0; i < maxn; i++) v[i].clear(); for(int i = 1; i <= N; i++) SM[i] = SM[i-1] + i; auto f = [&](int n, int cost, int top, int lim){ assert(top <= n); int sm = 0, bst = 0; for(int i = 0; i <= top; i++){ if(i * cost > lim) break; bst = max(bst, sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))]); sm+= n-i; } sm = 0; int bstid = -1; for(int i = 0; i <= top; i++){ if(i * cost > lim) break; int num = sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))]; if(num == bst){ if(bstid == -1) bstid = i; if(bstid != i) return -1; } sm+= n-i; } return bstid; }; for(int top = 100; top >= 1; top--){ for(int cost = 2; top * (cost-1) <= 100; cost++){ int x = f(100, cost, top, 100); if(x != -1) v[top].PB({x, cost}); } } queue<int> q; h[N] = 0; q.push(N); while(sz(q)){ int u = q.front(); q.pop(); for(pii p : v[u]) if(h[p.F] == -1) pr[p.F] = {u, p.S}, h[p.F] = h[u] + 1, q.push(p.F); } vector<pii> tdo; int tmp = 1; while(tmp != N){ tdo.PB(pr[tmp]); tmp = pr[tmp].F; } reverse(tdo.begin(), tdo.end()); vector<int> big; for(int i = 0; i < N; i++){ big.PB(i); } int A[maxn], B[maxn]; bool inside[maxn]; for(pii p : tdo){ memset(A, 0, sizeof A); memset(B, 0, sizeof B); memset(inside, 0, sizeof inside); for(int id : big) A[id] = p.S-1, inside[id] = 1; playRound(A, B); big.clear(); for(int i = 0; i < N; i++){ if(inside[i] && B[i] >= p.S) big.PB(i); } } assert(sz(big) == 1); return big[0]; } bool comp(int a, int b){ int A[maxn], B[maxn]; for(int d : {9, 5, 3, 1}){ memset(A, 0, sizeof A); memset(B, 0, sizeof B); A[a] = d, A[b] = d; playRound(A, B); bool X = B[a] > d, Y = B[b] > d; if(X ^ Y){ if(X) return 0; else return 1; } } assert(0); } int greaterValue(int N, int W) { return comp(0, 1); } void allValues(int N, int W, int *P) { if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. } else { int A[maxn], B[maxn]; for(int i = 0; i < N; i++) P[i] = 0; memset(A, 0, sizeof A); fill(A, A+N, 1); playRound(A, B); set<int> big; vector<int> vec, del; for(int i = 0; i < N; i++){ if(B[i] > 1) big.insert(i), vec.PB(i); } int NXT = N/2; while(sz(vec) > 1){ del.PB(vec.back()); vec.pop_back(); del.PB(vec.back()); vec.pop_back(); for(int i = 0; i < N; i++) A[i] = 1; for(int i : del) A[i] = 0; playRound(A, B); for(int i = 0; i < N; i++){ if(big.count(i) == 0 && B[i] > A[i]) big.insert(i), vec.PB(i), P[i] = NXT, NXT--; } } assert(sz(vec) == 1 && sz(big) == N-1 && NXT == 1); for(int i = 0; i < N; i++){ if(big.count(i) == 0) P[i] = 1; } vector<int> extra; for(int i = 0; i < N; i++) if(P[i] == 0) extra.PB(i); sort(extra.begin(), extra.end(), [](int a, int b){ return comp(a, b); }); assert(sz(extra) == N/2); for(int i = 0; i < sz(extra); i++) P[extra[i]] = N/2 + i + 1; } }
#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...