oj.uz

Submission #789679

# Submission time Handle Problem Language Result Execution time Memory
789679 2023-07-21T18:00:25 Z PoonYaPat Monster Game (JOI21_monster) C++17
0 / 100
 98 ms 4372 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 cntA=0, cntB=0, st;
  for (int i=0; i<n; ++i) {
    if (i==0) continue;
    if (Q(v[0],v[i])) {
      ++cntA;
      if (cntA>1) break; 
    }
  }
  
  for (int i=0; i<n; ++i) {
    if (i==1) continue;
    if (Q(v[1],v[i])) {
      ++cntB;
      if (cntB>1) break;
    }
  }

  if (cntA==1 && cntB==1) st=1;
  else if (cntA==1) st=0;
  else {
    int l=2, r=n-1;
    while (l<r) {
      int mid=(l+r)/2;
      if (!Q(v[0],v[mid])) r=mid;
      else l=mid+1;
    }
    if (Q(v[l-1],v[l-3])) st=l-2;
    else st=l-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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 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 Correct 2 ms 4176 KB Output is correct
7 Correct 2 ms 4176 KB Output is correct
8 Correct 2 ms 4176 KB Output is correct
9 Correct 2 ms 4176 KB Output is correct
10 Incorrect 2 ms 4176 KB Wrong Answer [3]
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4176 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 Correct 2 ms 4176 KB Output is correct
7 Correct 2 ms 4176 KB Output is correct
8 Correct 2 ms 4176 KB Output is correct
9 Correct 2 ms 4176 KB Output is correct
10 Incorrect 2 ms 4176 KB Wrong Answer [3]
11 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 96 ms 4244 KB Partially correct
2 Partially correct 77 ms 4252 KB Partially correct
3 Partially correct 98 ms 4260 KB Partially correct
4 Partially correct 49 ms 4252 KB Partially correct
5 Partially correct 69 ms 4256 KB Partially correct
6 Correct 60 ms 4256 KB Output is correct
7 Correct 63 ms 4240 KB Output is correct
8 Partially correct 93 ms 4176 KB Partially correct
9 Incorrect 63 ms 4372 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -