oj.uz

Submission #788843

# Submission time Handle Problem Language Result Execution time Memory
788843 2023-07-20T16:42:30 Z Boas Stray Cat (JOI20_stray) C++17
76 / 100
 1857 ms 14336 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

namespace
{
  int a, m;
}

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;

void doStuff(const bool &debug, const int &i, const vi &arr, const int &j, const int &mark, vi &lijn, vi &X, const vi &graad, vvi &lijnen, queue<tuple<int, int, vector<int>>> &q)
{
  if (debug)
    cerr << "Road from " << i << " to " << arr[j] << " gets mark " << mark << endl;
  X[j] = mark;
  if (graad[i] != 2)
  {
    if (lijn.size() >= 4)
    {
      lijnen.push_back(lijn);
    }
    lijn.clear();
  }
  if (graad[i] != 2 && graad[arr[j]] != 2)
  {
    q.push({arr[j], (mark - 1 + a) % a, lijn});
  }
  else
  {
    vi newLijn(lijn);
    newLijn.push_back(j);
    q.push({arr[j], (mark - 1 + a) % a, newLijn});
  }
}
constexpr bool debug = false;
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V)
{
  a = A;
  m = M;
  vector<int> X(M, -1);
  vector<int> graad(N);
  for (int i : U)
    graad[i]++;
  for (int i : V)
    graad[i]++;
  queue<tuple<int, int, vector<int>>> q;
  q.push({0, A - 1, {}});
  vector<vi> lijnen;
  while (!q.empty())
  {
    auto [i, mark, lijn] = q.front();
    q.pop();
    bool isEnd = true;
    for (int j = 0; j < m; j++)
    {
      if (X[j] != -1)
        continue;
      if (U[j] == i)
      {
        isEnd = false;
        doStuff(debug, i, V, j, mark, lijn, X, graad, lijnen, q);
      }
      else if (V[j] == i)
      {
        isEnd = false;
        doStuff(debug, i, U, j, mark, lijn, X, graad, lijnen, q);
      }
    }
    if (isEnd && lijn.size() >= 4)
      lijnen.push_back(lijn);
  }
  vi pattern = {0, 0, 1, 0, 1, 1};
  for (const auto &lijn : lijnen)
  {
    if (lijn.size() < 4)
      continue;
    int d = 0;
    while (X[lijn[0]] != pattern[(d) % 6] || X[lijn.back()] != pattern[(d + lijn.size() - 1) % 6])
    {
      d++;
      if (d > 1000)
      {
        break;
      }
    }
    for (uint32_t i = 0; i < lijn.size(); i++)
    {
      int mark = pattern[(i + d) % 6];
      if (debug)
        cerr << "Lijn van " << U[lijn[i]] << " naar " << V[lijn[i]] << " krijgt mark " << mark << endl;
      X[lijn[i]] = mark;
    }
  }
  return X;
}

#include "Catherine.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;

typedef vector<int> vi;
namespace
{
  vi prevMarks;
  int A, B;
  int prevMark = -1;
} // namespace

void Init(int A, int B)
{
  ::A = A;
  ::B = B;
  prevMarks.clear();
  prevMark = -1;
}

int calculateMove(vi &y)
{
  vector<int> leastOccurences = {};
  int least = (1 << 30);
  map<int, int> occurences;
  if (A == 2 && prevMark != -1)
  {
    y[prevMark]++;
  }

  for (int j = 0; j < A; ++j)
  {
    if (y[j] > 0)
    {
      if (y[j] < least)
      {
        least = y[j];
        leastOccurences = {j};
      }
      else if (y[j] == least)
      {
        leastOccurences.push_back(j);
      }
      occurences[j] = y[j];
    }
  }
  if (A > 2)
  {
    if (occurences.find(A - 1) != occurences.end() && occurences.find(0) != occurences.end())
    {
      return 0;
    }
    int max = 0;
    for (const auto &[j, c] : occurences)
    {
      max = std::max(j, max);
    }
    return max;
  }

  if (leastOccurences.size() == 0)
  {
    throw;
    return -1;
  }

  if (leastOccurences.size() == 1)
  {
    if (leastOccurences[0] == prevMark && y[leastOccurences[0]] == 1)
    {
      prevMarks.clear();
      return -1;
    }
    return leastOccurences[0];
  }
  if (leastOccurences.size() == 2)
  {
    // extra code for long straight lines with A = 2
    for (int i : leastOccurences)
    {
      if (i != prevMark) // when prevMark == -1, the 0 size is chosen
        return i;
    }
  }
  throw;
}

int Move(vi y)
{
  int sum = 0;
  for (int v : y)
    sum += v;
  int mark = calculateMove(y);
  if (A == 2 && sum == 1)
  {
    prevMarks.push_back(mark);
    int s = prevMarks.size();
    if (s > 3)
    {
      const vector<vi> turnAroundMarks = {
          {0, 0, 1, 0},
          {0, 1, 0, 1},
          {1, 0, 1, 1},
          {1, 1, 0, 0}};
      for (const auto &seq : turnAroundMarks)
      {
        for (int d = 0; d <= (int)turnAroundMarks.size() - 4; d++)
        {
          bool allEqual = true;
          for (int i = 0; i < 4; i++)
          {
            if (seq[i] != prevMarks[i + d])
            {
              allEqual = false;
              break;
            }
          }
          if (allEqual)
          {
            prevMarks.clear();
            return prevMark = -1;
          }
        }
      }
    }
  }
  else
    prevMarks.clear();
  return prevMark = mark;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1647 ms 14336 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1647 ms 14336 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1670 ms 12112 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1670 ms 12112 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 780 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 2 ms 908 KB Output is correct
5 Correct 3 ms 900 KB Output is correct
6 Correct 3 ms 900 KB Output is correct
7 Correct 3 ms 900 KB Output is correct
8 Correct 2 ms 912 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 3 ms 848 KB Output is correct
11 Correct 3 ms 912 KB Output is correct
12 Correct 2 ms 904 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 3 ms 908 KB Output is correct
15 Correct 2 ms 908 KB Output is correct
16 Correct 2 ms 772 KB Output is correct
17 Correct 2 ms 772 KB Output is correct
18 Correct 2 ms 780 KB Output is correct
19 Correct 3 ms 780 KB Output is correct
20 Correct 3 ms 772 KB Output is correct
21 Correct 2 ms 784 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 3 ms 784 KB Output is correct
24 Correct 2 ms 780 KB Output is correct
25 Correct 2 ms 780 KB Output is correct
26 Correct 2 ms 772 KB Output is correct
27 Correct 2 ms 772 KB Output is correct
28 Correct 2 ms 768 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1647 ms 10452 KB Output is correct
2 Correct 1654 ms 10996 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1041 ms 10348 KB Output is correct
5 Correct 1857 ms 12056 KB Output is correct
6 Correct 1823 ms 11924 KB Output is correct
7 Correct 1836 ms 10968 KB Output is correct
8 Correct 1815 ms 10980 KB Output is correct
9 Correct 1827 ms 12036 KB Output is correct
10 Correct 1853 ms 11884 KB Output is correct
11 Correct 1841 ms 11988 KB Output is correct
12 Correct 1833 ms 12044 KB Output is correct
13 Correct 1825 ms 12040 KB Output is correct
14 Correct 1829 ms 12148 KB Output is correct
15 Correct 1833 ms 12368 KB Output is correct
16 Correct 1829 ms 12016 KB Output is correct
17 Correct 1827 ms 11624 KB Output is correct
18 Correct 1852 ms 11688 KB Output is correct
19 Correct 1828 ms 11732 KB Output is correct
20 Correct 1841 ms 12024 KB Output is correct
21 Correct 1823 ms 11624 KB Output is correct
22 Correct 1831 ms 11724 KB Output is correct
23 Correct 1652 ms 10540 KB Output is correct
24 Correct 1648 ms 10460 KB Output is correct
25 Correct 1664 ms 10744 KB Output is correct
26 Correct 1651 ms 10856 KB Output is correct
27 Correct 1649 ms 11044 KB Output is correct
28 Correct 1643 ms 11028 KB Output is correct
29 Correct 1673 ms 11360 KB Output is correct
30 Correct 1644 ms 11164 KB Output is correct
31 Correct 1660 ms 10516 KB Output is correct
32 Correct 1642 ms 10492 KB Output is correct
33 Correct 1708 ms 10760 KB Output is correct
34 Correct 1673 ms 10656 KB Output is correct
35 Correct 1688 ms 10984 KB Output is correct
36 Correct 1672 ms 11068 KB Output is correct
37 Correct 1660 ms 10932 KB Output is correct
38 Correct 1664 ms 11008 KB Output is correct
39 Correct 1660 ms 11000 KB Output is correct
40 Correct 1666 ms 10896 KB Output is correct
41 Correct 1672 ms 11412 KB Output is correct
42 Correct 1686 ms 11500 KB Output is correct
43 Correct 1663 ms 11416 KB Output is correct
44 Correct 1686 ms 11788 KB Output is correct
45 Correct 1663 ms 11512 KB Output is correct
46 Correct 1674 ms 11568 KB Output is correct
47 Correct 1654 ms 10872 KB Output is correct
48 Correct 1648 ms 11008 KB Output is correct
49 Correct 1672 ms 10848 KB Output is correct
50 Correct 1656 ms 11104 KB Output is correct
51 Correct 1650 ms 10680 KB Output is correct
52 Correct 1666 ms 10748 KB Output is correct
53 Correct 1669 ms 10724 KB Output is correct
54 Correct 1704 ms 10788 KB Output is correct
55 Correct 1708 ms 10672 KB Output is correct
56 Correct 1680 ms 10576 KB Output is correct
57 Correct 1692 ms 10592 KB Output is correct
58 Correct 1678 ms 10692 KB Output is correct
59 Correct 1642 ms 10868 KB Output is correct
60 Correct 1648 ms 10924 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1644 ms 10380 KB Output is correct
2 Correct 1666 ms 10668 KB Output is correct
3 Correct 1 ms 524 KB Output is correct
4 Correct 1220 ms 10356 KB Output is correct
5 Correct 1834 ms 11900 KB Output is correct
6 Correct 1851 ms 11900 KB Output is correct
7 Incorrect 1817 ms 10936 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -