Submission #1178560

#TimeUsernameProblemLanguageResultExecution timeMemory
1178560amine_arouaKoala Game (APIO17_koala)C++20
66 / 100
35 ms460 KiB
#include "koala.h" #include<bits/stdc++.h> using namespace std; int sub = 0; int minValue(int N, int W) { // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int B[N] , R[N]; B[0] = 1; for(int i = 1 ; i < N ;i++) { B[i] = 0; R[i] = 0; } playRound(B , R); for(int i = 0 ;i < N ; i++) { if(R[i] <= B[i]) { return i; } } return 0; } int maxValue(int N, int W) { // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int B[N] , R[N]; // cout<<"HELLO\n"; for(int i = 0 ; i < N ;i++) { B[i] = 1; R[i] = 0; } int nb1 = N; int ret = 0; vector<bool> bad(N); while(nb1 > 1) { // cout<<"B : "; // for(int i = 0 ; i < N ; i++) // { // cout<<B[i]<<" "; // } // cout<<'\n'; playRound(B , R); // cout<<"R : "; // for(int i = 0 ; i < N ; i++) // { // cout<<R[i]<< " "; // } // cout<<'\n'; nb1 = 0; for(int i = 0 ; i < N ; i++) { if(bad[i]) continue; if(R[i] <= B[i]) { bad[i] = 1; B[i] = 0; } else { B[i]++; nb1++; ret = i; } } } return ret; } int greaterValue(int N, int W) { // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int lo = 0 , hi = 10; int a = 0 , b = 1; while(lo + 1 < hi) { int md = (lo + hi) / 2ll; int B[N] , R[N]; for(int i = 0 ; i < N ; i++) { B[i] = 0; R[i] = 0; } B[a] = md; B[b] = md; playRound(B , R); int aa = (R[a] > B[a]); int bb = (R[b] > B[b]); if(aa == 0 && bb == 0) { hi = md; } else if(aa == 1 && bb == 1) { lo = md; } else return bb; } return 1; } bool cmp(const int &a, const int &b ) { int N = 100; if(a == b) return 0; if(sub == 0) { int B[N] , R[N]; for(int i = 0 ; i < N ; i++) { B[i] = 0 , R[i] = 0; } B[a] = N; B[b] = N; playRound(B , R); if(R[b] > B[b]) return 1; return 0; } else { int lo = 0 , hi = 10; while(lo + 1 < hi) { int md = (lo + hi) / 2ll; int B[N] , R[N]; for(int i = 0 ; i < N ; i++) { B[i] = 0; R[i] = 0; } B[a] = md; B[b] = md; playRound(B , R); int aa = (R[a] > B[a]); int bb = (R[b] > B[b]); if(aa == 0 && bb == 0) { hi = md; } else if(aa == 1 && bb == 1) { lo = md; } else return bb; } return 1; } } void merge(vector<int> &arr, int l, int mid, int r) { int n1 = mid - l + 1; int n2 = r - mid; vector<int> L(n1), R(n2); for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (cmp(L[i], R[j])) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void Sort(vector<int> &arr, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; Sort(arr, l, mid); Sort(arr, mid + 1, r); merge(arr, l, mid, r); } 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. vector<int> order(N); iota(order.begin() , order.end() , 0); Sort(order , 0 , N - 1); for(int i = 0 ; i < N ; i++) { P[order[i]] = i + 1; } } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. sub = 1; vector<int> order(N); iota(order.begin() , order.end() , 0); Sort(order , 0 , N - 1); for(int i = 0 ; i < N ; i++) { P[order[i]] = 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...