Submission #129761

#	Time	Username	Problem	Language	Result	Execution time	Memory
129761		tjd229	Minerals (JOI19_minerals)	C++14	40 / 100	96 ms	3924 KiB

minerals

#include "minerals.h"
#include <vector>
using namespace std;
int l[43000], r[43000],m[43000];
int ans[43000];
void Solve(int N) {
   int NN = N + N;
   int last = 0;
   vector<int> X,Y;
   
   for (int i = 1; i <= NN; ++i) {
      int in = Query(i);
      if (in == last) {
         int yix = Y.size();
         l[yix] = 0, r[yix] = X.size() - 1;
         Y.push_back(i);
      }
      else X.push_back(i);
      last = in;
   }
   
   int dir = 1;
   while (1) {
      vector<int> v[43000];//ix li
      int in = 0;
      for (int i = 0; i < N; ++i) {
         if (l[i] <= r[i]) {
            m[i] = (l[i] + r[i]) >> 1;
            v[m[i]].push_back(i);//yix
            ++in;
         }
      }
      if (in == 0) break;
      if (dir) {
         for (int i = N - 1; i >= 0; --i) {
            for (auto yix : v[i]) {
               int y = Y[yix];
               in = Query(y);
               if (in == last) r[yix] = i - 1, ans[yix] = i;
               else l[yix] = i + 1;
               last = in;
            }
            last = Query(X[i]);
         }
      }
      else {
         for (int i = 0; i < N; ++i) {
            last = Query(X[i]);
            for (auto yix : v[i]) {
               int y = Y[yix];
               in = Query(y);
               if (in == last) r[yix] = i - 1, ans[yix] = i;
               else l[yix] = i + 1;
               last = in;
            }
         }
      }
      dir = 1 - dir;
   }
   for (int i = 0; i < N; ++i)
      Answer(X[ans[i]],Y[i]);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10