제출 #1170000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170000		owieczka	Minerals (JOI19_minerals)	C++20	40 / 100	12 ms	7012 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int base = 1 << 15;
// int group[30'002];
int in[30'002];
int n;
vector<int> group[60'002];
vector<int> cors[60'002];

void bipart()
{
  int last = 0;
  for (int i = 1; i <= 2 * n; i++)
  {
    int a = Query(i);
    if (a == last)
    {
      cors[1].push_back(i);
      Query(i);
    }
    else 
    {
      group[1].push_back(i);
      in[i] = 1;
    }
    last = a;
  }
  for (int i = 1; i <= 2*n; i++)
  {
    if (in[i])
    {
      in[i] = 0;
      Query(i);
    }
  }
  

}

void divide(int g)
{
  int i = 0;
  int last = 0;
  if (group[g].size() <= 1)return;
  for (; i * 2 < group[g].size(); i++) // wrzucam 1 pol
  {
    last = Query(group[g][i]);
    group[g*2].push_back(group[g][i]);
  }
  for (; i < group[g].size(); i++)
  {
    group[g*2+1].push_back(group[g][i]);
  }
  for (auto i : cors[g])
  {
    int a = Query(i);
    if (last == a)
    {
      Query(i);
      cors[g*2].push_back(i);
    }
    else
    {
      Query(i);
      cors[g*2+1].push_back(i);
    }
  }
  for (int i = 0; i * 2 < group[g].size(); i++)
  {
    Query(group[g][i]);
  }
  divide(g*2);
  divide(g*2+1);
}

void Solve(int N) {
  n = N;
  // for (int i = 1; i <= N; ++i) {
  //   Answer(i, 2 * N + 1 - i);
  // }
  bipart();
  divide(1);
  for (int i = 1; i <= 4*n; i++)
  {
    if (group[i].size() == 1)
    {
      Answer(group[i][0], cors[i][0]);
    }
  }
}

• 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