oj.uz

Submission #788914

# Submission time Handle Problem Language Result Execution time Memory
788914 2023-07-20T17:20:06 Z Boas Stray Cat (JOI20_stray) C++17
91 / 100
 1941 ms 15708 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 (a == 2 && graad[i] != 2)
  {
    if (lijn.size() >= 4)
    {
      lijnen.push_back(lijn);
    }
    lijn.clear();
  }
  if (a != 2 || (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});
  }
}
 
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V)
{
bool debug = false;
  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 (A == 2 && 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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1686 ms 14536 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1061 ms 14180 KB Output is correct
4 Correct 1690 ms 15708 KB Output is correct
5 Correct 1692 ms 15656 KB Output is correct
6 Correct 1705 ms 14332 KB Output is correct
7 Correct 1690 ms 14332 KB Output is correct
8 Correct 1695 ms 15096 KB Output is correct
9 Correct 1693 ms 15064 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1686 ms 14536 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1061 ms 14180 KB Output is correct
4 Correct 1690 ms 15708 KB Output is correct
5 Correct 1692 ms 15656 KB Output is correct
6 Correct 1705 ms 14332 KB Output is correct
7 Correct 1690 ms 14332 KB Output is correct
8 Correct 1695 ms 15096 KB Output is correct
9 Correct 1693 ms 15064 KB Output is correct
10 Correct 1641 ms 12752 KB Output is correct
11 Correct 1628 ms 12828 KB Output is correct
12 Correct 1680 ms 12512 KB Output is correct
13 Correct 1684 ms 12496 KB Output is correct
14 Correct 1686 ms 12740 KB Output is correct
15 Correct 1682 ms 13144 KB Output is correct
16 Correct 1686 ms 15196 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1680 ms 12128 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1583 ms 11984 KB Output is correct
4 Correct 1692 ms 13544 KB Output is correct
5 Correct 1691 ms 13536 KB Output is correct
6 Correct 1684 ms 12220 KB Output is correct
7 Correct 1684 ms 12160 KB Output is correct
8 Correct 1695 ms 12768 KB Output is correct
9 Correct 1684 ms 12800 KB Output is correct
10 Correct 1698 ms 12508 KB Output is correct
11 Correct 1684 ms 12516 KB Output is correct
12 Correct 1690 ms 12520 KB Output is correct
13 Correct 1680 ms 12512 KB Output is correct
14 Correct 1684 ms 12896 KB Output is correct
15 Correct 1688 ms 12892 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1680 ms 12128 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1583 ms 11984 KB Output is correct
4 Correct 1692 ms 13544 KB Output is correct
5 Correct 1691 ms 13536 KB Output is correct
6 Correct 1684 ms 12220 KB Output is correct
7 Correct 1684 ms 12160 KB Output is correct
8 Correct 1695 ms 12768 KB Output is correct
9 Correct 1684 ms 12800 KB Output is correct
10 Correct 1698 ms 12508 KB Output is correct
11 Correct 1684 ms 12516 KB Output is correct
12 Correct 1690 ms 12520 KB Output is correct
13 Correct 1680 ms 12512 KB Output is correct
14 Correct 1684 ms 12896 KB Output is correct
15 Correct 1688 ms 12892 KB Output is correct
16 Correct 1941 ms 10820 KB Output is correct
17 Correct 1936 ms 10912 KB Output is correct
18 Correct 1682 ms 10588 KB Output is correct
19 Correct 1682 ms 10592 KB Output is correct
20 Correct 1680 ms 11216 KB Output is correct
21 Correct 1680 ms 10952 KB Output is correct
22 Correct 1693 ms 13244 KB Output is correct
23 Correct 1679 ms 10696 KB Output is correct
24 Correct 1687 ms 10728 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 772 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 2 ms 908 KB Output is correct
5 Correct 2 ms 864 KB Output is correct
6 Correct 3 ms 900 KB Output is correct
7 Correct 3 ms 964 KB Output is correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 3 ms 900 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 908 KB Output is correct
12 Correct 2 ms 908 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 3 ms 900 KB Output is correct
15 Correct 3 ms 908 KB Output is correct
16 Correct 3 ms 772 KB Output is correct
17 Correct 2 ms 780 KB Output is correct
18 Correct 2 ms 772 KB Output is correct
19 Correct 3 ms 808 KB Output is correct
20 Correct 2 ms 772 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 2 ms 772 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 780 KB Output is correct
25 Correct 3 ms 864 KB Output is correct
26 Correct 2 ms 780 KB Output is correct
27 Correct 3 ms 740 KB Output is correct
28 Correct 2 ms 868 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1692 ms 10388 KB Output is correct
2 Correct 1688 ms 11008 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Correct 1049 ms 10408 KB Output is correct
5 Correct 1867 ms 11968 KB Output is correct
6 Correct 1861 ms 12024 KB Output is correct
7 Correct 1857 ms 10972 KB Output is correct
8 Correct 1853 ms 11044 KB Output is correct
9 Correct 1860 ms 12056 KB Output is correct
10 Correct 1858 ms 11924 KB Output is correct
11 Correct 1865 ms 12072 KB Output is correct
12 Correct 1866 ms 11924 KB Output is correct
13 Correct 1864 ms 11988 KB Output is correct
14 Correct 1861 ms 11992 KB Output is correct
15 Correct 1863 ms 11924 KB Output is correct
16 Correct 1854 ms 12104 KB Output is correct
17 Correct 1874 ms 13356 KB Output is correct
18 Correct 1855 ms 11572 KB Output is correct
19 Correct 1861 ms 11620 KB Output is correct
20 Correct 1855 ms 11700 KB Output is correct
21 Correct 1865 ms 11516 KB Output is correct
22 Correct 1859 ms 13400 KB Output is correct
23 Correct 1674 ms 10484 KB Output is correct
24 Correct 1678 ms 10620 KB Output is correct
25 Correct 1688 ms 10872 KB Output is correct
26 Correct 1694 ms 10724 KB Output is correct
27 Correct 1703 ms 11024 KB Output is correct
28 Correct 1684 ms 11292 KB Output is correct
29 Correct 1690 ms 11128 KB Output is correct
30 Correct 1684 ms 11384 KB Output is correct
31 Correct 1678 ms 10476 KB Output is correct
32 Correct 1680 ms 10424 KB Output is correct
33 Correct 1691 ms 10624 KB Output is correct
34 Correct 1682 ms 10696 KB Output is correct
35 Correct 1682 ms 11032 KB Output is correct
36 Correct 1686 ms 10836 KB Output is correct
37 Correct 1692 ms 10900 KB Output is correct
38 Correct 1690 ms 10892 KB Output is correct
39 Correct 1705 ms 10952 KB Output is correct
40 Correct 1718 ms 10888 KB Output is correct
41 Correct 1693 ms 11440 KB Output is correct
42 Correct 1718 ms 11408 KB Output is correct
43 Correct 1742 ms 11492 KB Output is correct
44 Correct 1726 ms 11564 KB Output is correct
45 Correct 1706 ms 11524 KB Output is correct
46 Correct 1700 ms 11568 KB Output is correct
47 Correct 1700 ms 10828 KB Output is correct
48 Correct 1713 ms 11040 KB Output is correct
49 Correct 1704 ms 10796 KB Output is correct
50 Correct 1689 ms 11008 KB Output is correct
51 Correct 1696 ms 10640 KB Output is correct
52 Correct 1702 ms 10656 KB Output is correct
53 Correct 1688 ms 10724 KB Output is correct
54 Correct 1702 ms 10704 KB Output is correct
55 Correct 1682 ms 10740 KB Output is correct
56 Correct 1713 ms 10656 KB Output is correct
57 Correct 1695 ms 10696 KB Output is correct
58 Correct 1686 ms 10636 KB Output is correct
59 Correct 1682 ms 10860 KB Output is correct
60 Correct 1684 ms 10896 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 10380 KB Output is correct
2 Correct 1698 ms 10812 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1212 ms 10356 KB Output is correct
5 Correct 1874 ms 13920 KB Output is correct
6 Correct 1877 ms 12212 KB Output is correct
7 Incorrect 1871 ms 11772 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -