oj.uz

답안 #789396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789396 2023-07-21T10:21:08 Z PoonYaPat Monster Game (JOI21_monster) C++17
0 / 100
 64 ms 4240 KB 
#include "monster.h"
#include <bits/stdc++.h>
using namespace std;

int val[1005][1005];
vector<int> v;

void rev(int l, int r) {
  while (l<r) {
    swap(v[l],v[r]);
    ++l; --r;
  }
}

int Q(int a, int b) {
  if (val[a][b]==-1) {
    int k=Query(a,b);
    val[a][b]=k;
    val[b][a]=1-k;
  }
  return val[a][b];
}

vector<int> merge_sort(int l, int r) {
  if (l==r) return {l};

  int mid=(l+r)/2;
  vector<int> L=merge_sort(l,mid), R=merge_sort(mid+1,r), res;

  int idL=0, idR=0;
  while (idL<L.size() && idR<R.size()) {
    if (!Q(L[idL],R[idR])) res.push_back(L[idL++]);
    else res.push_back(R[idR++]);
  }

  while (idL<L.size()) res.push_back(L[idL++]);
  while (idR<R.size()) res.push_back(R[idR++]);
  return res;
}

vector<int> Solve(int N) {
  memset(val,-1,sizeof(val));
  int n=N;
  v=merge_sort(0,n-1);
  
  int cnt=0,st=0,pos=-1;
  for (int i=1; i<n; ++i) if (Q(v[0],v[i])) {
    ++cnt;
    if (cnt==1) pos=i;
    else {
      pos=-1;
      break;
    }
  }

  if (pos!=-1) {
    if (!Q(v[st],v[pos])) swap(pos,st);
  } else {
    for (int i=2; i<n; ++i) {
      if (!Q(v[0],v[i])) {
        if (Q(v[i-1],v[i-3])) st=i-2;
        else st=i-1;
      }
    }
  }

  rev(0,st);
  int idx=st+1;
  while (idx<n) {
    int x=idx-1;
    while (!Q(v[x],v[idx]) && idx<n) ++idx;
    rev(x+1,idx);
    ++idx;
  }

  vector<int> ans(n);
  for (int i=0; i<n; ++i) ans[v[i]]=i;
  return ans;
}

Compilation message

monster.cpp: In function 'std::vector<int> merge_sort(int, int)':
monster.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while (idL<L.size() && idR<R.size()) {
      |          ~~~^~~~~~~~~
monster.cpp:31:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while (idL<L.size() && idR<R.size()) {
      |                          ~~~^~~~~~~~~
monster.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while (idL<L.size()) res.push_back(L[idL++]);
      |          ~~~^~~~~~~~~
monster.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   while (idR<R.size()) res.push_back(R[idR++]);
      |          ~~~^~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4140 KB Output is correct
2 Correct 2 ms 4176 KB Output is correct
3 Correct 2 ms 4176 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 2 ms 4176 KB Output is correct
6 Incorrect 2 ms 4176 KB Wrong Answer [3]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4140 KB Output is correct
2 Correct 2 ms 4176 KB Output is correct
3 Correct 2 ms 4176 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 2 ms 4176 KB Output is correct
6 Incorrect 2 ms 4176 KB Wrong Answer [3]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 4240 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -