oj.uz

Submission #789677

# Submission time Handle Problem Language Result Execution time Memory
789677 2023-07-21T17:53:07 Z PoonYaPat Monster Game (JOI21_monster) C++17
0 / 100
 89 ms 4304 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; 
    } else 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 {
    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;
        break;
      }
    }
  }

  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++]);
      |          ~~~^~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:75:7: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |   int idx=st+1;
      |       ^~~

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 Incorrect 2 ms 4176 KB Wrong Answer [3]
6 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 Incorrect 2 ms 4176 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 88 ms 4304 KB Partially correct
2 Partially correct 85 ms 4240 KB Partially correct
3 Partially correct 89 ms 4240 KB Partially correct
4 Partially correct 51 ms 4244 KB Partially correct
5 Partially correct 88 ms 4176 KB Partially correct
6 Correct 78 ms 4252 KB Output is correct
7 Correct 74 ms 4176 KB Output is correct
8 Partially correct 88 ms 4252 KB Partially correct
9 Incorrect 69 ms 4176 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -