oj.uz

Submission #1079557

# Submission time Handle Problem Language Result Execution time Memory
1079557 2024-08-28T16:56:54 Z bleahbleah Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 67664 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
#define sz(x) ((int)(x).size())

int K, N;
const int nmax = 2e5 + 5;

namespace Queue {
   int next[nmax];
   int inside[nmax];
   
   set<int> heads;
   void insert(int node) {
      heads.emplace(node);
      inside[node] = 1;
      next[node] = -1;
      for(int i = (node + 1) % N, d = 1; i != node && d < K; d++, i = (i + 1) % N) {
         if(inside[i]) {
            if(heads.count(i))
               heads.erase(i);
            next[node] = i;
            break;
         }
      }
      for(int i = (node - 1 + N) % N, d = 1; i != node && d < K; d++, i = (i - 1 + N) % N) {
         if(inside[i]) {
            heads.erase(node);
            next[i] = node;
            break;
         }
      }
   }
   
   vector<int> prune() {
      vector<int> rez;
      for(auto x : heads)
         rez.emplace_back(x), inside[x] = 0;
      heads.clear();
      for(auto x : rez)
         if(next[x] != -1) heads.emplace(next[x]);
      return rez;
   }
}

vector<int> topsort;
#define left ofia
#define right goa
int left[nmax][18], jumpl[nmax][18];
int right[nmax][18], jumpr[nmax][18];

void init(int k__, std::vector<int> r) {
   auto T = r;
   K = k__;
   N = sz(r);
   topsort.resize(N);
   
   vector<int> erased(N, 0);
   for(int i = 0; i < sz(r); i++) 
      if(r[i] == 0) erased[i] = 1, Queue::insert(i);
   
   int color = 0;
   while(sz(Queue::heads)) {
      auto rem = Queue::prune();
      ++color;
      for(auto x : rem) topsort[x] = color;
      
      for(auto x : rem) {
         for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
            if(erased[i]) continue;
            r[i]--;
            if(r[i] == 0) erased[i] = 1, Queue::insert(i);
         }
      }
   }
   
   for(int x = 0; x < sz(r); x++) {
      int mn = -1;
      jumpl[x][0] = 0;
      for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
         if(topsort[i] > topsort[x])
            mn = (mn == -1? jumpl[x][0] = d, i : topsort[mn] < topsort[i]? mn : jumpl[x][0] = d, i);
      }
      left[x][0] = mn == -1? x : mn;
      
      mn = -1;
      jumpr[x][0] = 0;
      for(int i = (x + 1 + N) % N, d = 1; d < K; d++, i = (i + 1 + N) % N) {
         if(topsort[i] > topsort[x])
            mn = (mn == -1? jumpr[x][0] = d, i : topsort[mn] < topsort[i]? mn : jumpr[x][0] = d, i);
      }
      right[x][0] = mn == -1? x : mn;
      //cerr << x << ": " << left[x][0] << ' ' << right[x][0] << '\t' << jumpl[x][0] << ' ' << jumpr[x][0] << '\n';
   }
   for(int step = 1; step < 18; step++)
      for(int i = 0; i < N; i++)
         left[i][step] = left[left[i][step - 1]][step - 1], jumpl[i][step] = jumpl[i][step - 1] + jumpl[left[i][step - 1]][step - 1],
         right[i][step] = right[right[i][step - 1]][step - 1], jumpr[i][step] = jumpr[i][step - 1] + jumpr[right[i][step - 1]][step - 1];
   
   //for(auto x : topsort) cerr << x << ' ';
   //cerr << '\n';
   
   
   //for(int i= 0; i < N; i++) {
      //cerr << i << "/";
      //if(erased[i]) cerr << -1;
      //else cerr << r[i] << "/" << T[i];;
      //cerr << ' ';
   //}
   //cerr << '\n';
      
   
	return;
}

bool compare_smaller(int x, int y) {
   //cerr << x << " vs " << y << '\n';
   auto rdist = [&](int d) {
      return d < x? N - x + d : d - x;
   };
   auto ldist = [&](int d) {
      return d <= x? x - d : x + N - d;
   };
   
   int st = x, buffer = rdist(y);
   for(int i = 17; i >= 0; i--) {
      if(buffer < jumpr[st][i]) continue;
      buffer -= jumpr[st][i];
      st = right[st][i];
   }
   
   //cerr << "rightmost: " << x << ' ' << st << ' ' << y << "\t\t" << rdist(y) << ' ' << rdist(st) << ' ' << topsort[st] << ' ' << topsort[x] << '\n';
   //for(int i = 0; i < N; i++) cerr << ldist(i) << ' ';
   //cerr << '\n';
   
   if(st == y) return 1;
   if(rdist(y) - rdist(st) < K && topsort[y] > topsort[st]) return 1;
   
   st = x;
   buffer = ldist(y);
   for(int i = 17; i >= 0; i--) {
      if(buffer < jumpl[st][i]) continue;
      buffer -= jumpl[st][i];
      st = left[st][i];
   }
   
   
   //cerr << "leftmost: " << x << ' ' << st << ' ' << y << "\t\t" << ldist(y) << ' ' << ldist(st) << ' ' << topsort[st] << ' ' << topsort[x] << '\n';
   
   if(st == y) return 1;
   if(ldist(y) - ldist(st) < K && topsort[y] > topsort[st]) return 1;
   return 0;
}

int compare_plants(int x, int y) {
   //cerr << x << ' ' << y << '\t' << compare_smaller(x, y) << '\t' << compare_smaller(y, x) << '\n';
   return topsort[x] > topsort[y]? -1 : 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 18 ms 836 KB Output is correct
7 Correct 520 ms 6640 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 18 ms 860 KB Output is correct
10 Correct 497 ms 6536 KB Output is correct
11 Correct 235 ms 6484 KB Output is correct
12 Correct 279 ms 6740 KB Output is correct
13 Correct 660 ms 6620 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 18 ms 836 KB Output is correct
7 Correct 520 ms 6640 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 18 ms 860 KB Output is correct
10 Correct 497 ms 6536 KB Output is correct
11 Correct 235 ms 6484 KB Output is correct
12 Correct 279 ms 6740 KB Output is correct
13 Correct 660 ms 6620 KB Output is correct
14 Execution timed out 4026 ms 9040 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 37 ms 5544 KB Output is correct
4 Correct 159 ms 67432 KB Output is correct
5 Correct 570 ms 67664 KB Output is correct
6 Execution timed out 4040 ms 59984 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -