제출 #528883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528883		schse	Monster Game (JOI21_monster)	C++17	0 / 100	76 ms	312 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

std::vector<int> SB1(int N)
{
  std::vector<int> T(N);
  vector<int> winns(N);
  vector<vector<bool>> answs(N, vector<bool>(N, false));
  for (int i = 0; i < N; i++)
    for (int e = 0; e < i; e++)
    {
      bool b = Query(i, e);
      winns[b ? i : e]++;
      answs[i][e] = b;
      answs[e][i] = !b;
    }
  vector<int> l, f;
  for (int i = 0; i < N; i++)
  {
    if (winns[i] == 1)
      f.push_back(i);
    else if (winns[i] == N - 2)
      l.push_back(i);
    else
      T[i] = winns[i];
  }
  if (answs[l[1]][l[0]])
    swap(l[0], l[1]);
  T[l[0]] = N - 2;
  T[l[1]] = N - 1;

  if (answs[f[1]][f[0]])
    swap(f[0], f[1]);
  T[f[0]] = 0;
  T[f[1]] = 1;

  for (int i = 0; i < N; i++)
  {
    cout << " " << T[i];
  }
  cout << endl;

  return T;
}

std::vector<int> merge(vector<int> pt1, vector<int> pt2)
{
  vector<int> arr;
  int a = 0, b = 0;
  while (a != pt1.size() || pt2.size() != b)
  {
    if (pt1.size() != a && (pt2.size() == b || !Query(pt1[a], pt2[b])))
    {
      arr.push_back(pt1[a++]);
    }
    else
    {
      arr.push_back(pt2[b++]);
    }
  }
  return arr;
}
std::vector<int> mergeSort(vector<int> arr)
{
  if (arr.size() <= 1)
    return arr;
  vector<int> pt1(arr.begin(), arr.begin() + arr.size() / 2);
  vector<int> pt2(arr.begin() + arr.size() / 2, arr.end());

  mergeSort(pt1);
  mergeSort(pt2);
  return merge(pt1, pt2);
}

std::vector<int> Solve(int N)
{

  if (!false && N <= 200)
  {
    return SB1(N);
  }

  vector<int> monsters(N);
  iota(monsters.begin(), monsters.end(), 0);
  monsters = mergeSort(monsters);

  /*for (int i = 0; i < N; i++)
  {
    cout << " " << S[monsters[i]];
  }
  cout << endl;*/

  int unSorted = 0;

  if (Query(monsters[0], monsters[1]))
  {
    unSorted++;
  }
  while (unSorted < N - 1)
  {
    int pivot = unSorted + 2;
    while (pivot < N && Query(monsters[unSorted], monsters[pivot]))
    {
      pivot++;
    }
    reverse(monsters.begin() + unSorted, monsters.begin() + pivot);
    unSorted=pivot;
  }

  /*for (int i = 0;   i < N; i++)
  {
    cout << " " << S[monsters[i]];
  }*/

  return monsters;
}

컴파일 시 표준 에러 (stderr) 메시지

monster.cpp: In function 'std::vector<int> merge(std::vector<int>, std::vector<int>)':
monster.cpp:54:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   while (a != pt1.size() || pt2.size() != b)
      |          ~~^~~~~~~~~~~~~
monster.cpp:54:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   while (a != pt1.size() || pt2.size() != b)
      |                             ~~~~~~~~~~~^~~~
monster.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if (pt1.size() != a && (pt2.size() == b || !Query(pt1[a], pt2[b])))
      |         ~~~~~~~~~~~^~~~
monster.cpp:56:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if (pt1.size() != a && (pt2.size() == b || !Query(pt1[a], pt2[b])))
      |                             ~~~~~~~~~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75