Submission #316875

#TimeUsernameProblemLanguageResultExecution timeMemory
316875spatarelComparing Plants (IOI20_plants)C++17
11 / 100
88 ms6136 KiB
#include "plants.h" #include <stdio.h> struct MoxRange { int mox; int l; int r; }; MoxRange getMoxRange(int k, std::vector<int> &r) { int n = r.size(); int i = n - 1; int positives = 0; while (i >= 0 && r[i] != 0) { i--; positives++; } int maxPositives = -1; int maxZero = 0; for (int i = 0; i < n; i++) { if (r[i] == 0 && maxPositives < positives) { maxPositives = positives; maxZero = i; } if (r[i] != 0) { positives++; } else { positives = 0; } //printf("i=%d posi=%d\n", i, positives); } MoxRange answer; answer.mox = maxZero; answer.l = maxZero - maxPositives; answer.r = maxZero + k - 1; //* if (answer.r - answer.l + 1 > n) { answer.r = answer.l + n - 1; } answer.l = (answer.l + n) % n; answer.r = (answer.r + n) % n;//*/ r[maxZero] = -1; i = maxZero; for (int i = 0; i < k - 1; i++) { maxZero = (maxZero - 1 + n) % n; r[maxZero]--; } return answer; } void print(std::vector<int> &r) { int n = r.size(); for (int i = 0; i < n; i++) { printf("%d ", r[i]); } printf("\n"); } const int MAX_N = 300; int gt[MAX_N][MAX_N]; void init(int k, std::vector<int> r) { int n = r.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { gt[i][j] = 0; } } for (int i = 0; i < n; i++) { //print(r); MoxRange moxRange = getMoxRange(k, r); //printf("%d > [%d..%d]\n", moxRange.mox, moxRange.l, moxRange.r); int x = moxRange.l; do { if (x != moxRange.mox && gt[x][moxRange.mox] == 0 && r[x] >= 0) { gt[moxRange.mox][x] = +1; gt[x][moxRange.mox] = -1; } x = (x + 1) % n; } while (x != (moxRange.r + 1) % n); } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int value : {-1, +1}) { if (gt[i][k] == value && gt[k][j] == value) { gt[i][j] = value; } } } } } /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d ", gt[i][j]); } printf("\n"); }//*/ return; } int compare_plants(int x, int y) { return gt[x][y]; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...