Submission #1169889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169889		owieczka	Minerals (JOI19_minerals)	C++20	6 / 100	123 ms	1112 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int base = 1 << 16;

// bitset <43'002> in;

int in[2 *base]; 
bool o[2 * 43'002];
int out[2 *base]; 
int matches[2 * 43'002];

void update_in(int c, int val)
{
  c += base;
  while (c)
  {
    in[c] += val;
    c /= 2;
  }
}
void update_out(int c, int val)
{
  c += base;
  while (c)
  {
    out[c] += val;
    c /= 2;
  }
}

int find_in(int x)
{
  int pref = 0;
  int c = 1;
  while (c < base)
  {
    if (pref + in[c*2] >= x)
    {
      c *= 2;
    }
    else 
    {
      pref += in[c*2];
      c = c * 2 + 1;
    }
  }
  return c - base;
}

int find_out(int x)
{
  int pref = 0;
  int c = 1;
  while (c < base)
  {
    if (pref + out[c*2] >= x)
    {
      c *= 2;
    }
    else 
    {
      pref += out[c*2];
      c = c * 2 + 1;
    }
  }
  return c - base;
}

void Solve(int N) {
  // for (int i = 1; i <= N; ++i) {
  //   Answer(i, 2 * N + 1 - i);
  // }
  for (int i = 1; i <= 2 * N; i++)
  {
    out[i+base] = 1;
  }
  for (int i = base - 1; i > 0; i--)
  {
    out[i] = out[i*2] + out[i*2+1];
  }
  mt19937 g(0);
  int v = g()%N+1;
  Query(v);
  update_in(v, 1);
  update_out(v, -1);
  v = find_out(g() % out[1] + 1);
  update_in(v, 1);
  update_out(v, -1);
  int a = Query(v); 
  if (a == 1)
  {
    update_in(v, -1);
  }
  int c_in = 2; // ile mi powinno pokazywac in
  int culp = v;

  while (out[1] + in[1] > 2)
  {
    if (a != c_in) // w srodku jest para zle
    {
      v = find_in(g() % in[1] + 1);
      int b = Query(v);
      update_in(v, -1);
      if (b == a) // znalazlem mathcing
      {
        matches[culp] = v;
        matches[v] = culp;
        c_in = a;
      }
      else // nic nie ma v jest out
      {
        update_out(v, 1);
        c_in--;
      }
      a = b;
    }
    else // wrzucam kolejne zeby sie pojawila para
    {
      v = find_out(g() % out[1] + 1);
      update_out(v, -1);
      int b = Query(v);
      c_in++;
      if (b == a) // wrzucilem do pary
      {
        culp = v;
      }
      else
      {
        update_in(v, 1);
      }
      a = b;
    }
  }
  int rem1=0, rem2=0;
  for (int i = 1; i <= 2 * N; i++)
  {
    if (o[i])continue;
    if (!matches[i])
    {
      if (!rem1)rem1 = i;
      else rem2 = i;
      continue;
    }
    Answer(i, matches[i]);
    o[i] = 1;
    o[matches[i]] = 1;
  }
  if (rem1 && rem2)Answer(rem1, rem2);
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 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