oj.uz

Submission #788671

# Submission time Handle Problem Language Result Execution time Memory
788671 2023-07-20T13:13:06 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 1974 ms 15728 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

namespace
{
  int a, m;
}

using namespace std;

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

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();
    for (int j = 0; j < m; j++)
    {
      if (X[j] != -1)
        continue;
      if (U[j] == i)
      {
        // cerr << "Road from " << i << " to " << V[j] << " gets mark " << mark << endl;
        X[j] = mark;
        if (graad[i] != 2)
          lijn.clear();
        if (A == 2 && i != 0 && graad[i] == 2)
        {
          vi newLijn(lijn);
          newLijn.push_back(j);
          if (graad[V[j]] != 2 && newLijn.size() > 3)
          {
            lijnen.push_back(newLijn);
          }
          q.push({V[j], (mark - 1 + a) % a, newLijn});
        }
        else
          q.push({V[j], (mark - 1 + a) % a, lijn});
      }
      else if (V[j] == i)
      {
        // cerr << "Road from " << i << " to " << U[j] << " gets mark " << mark << endl;
        X[j] = mark;
        if (graad[i] != 2)
          lijn.clear();
        if (A == 2 && i != 0 && graad[i] == 2)
        {
          vi newLijn(lijn);
          newLijn.push_back(j);
          if (graad[U[j]] != 2 && newLijn.size() > 3)
          {
            lijnen.push_back(newLijn);
          }
          q.push({U[j], (mark - 1 + a) % a, newLijn});
        }
        else
          q.push({U[j], (mark - 1 + a) % a, lijn});
      }
    }
  }
  vi pattern = {0, 0, 1, 0, 1, 1};
  for (const auto &lijn : lijnen)
  {
    if (lijn.size() < 4)
      continue;
    for (uint32_t i = 1; i < lijn.size() - 1; i++)
    {
      int mark = pattern[i % 6];
      // 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 1687 ms 14552 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1045 ms 14152 KB Output is correct
4 Correct 1702 ms 15728 KB Output is correct
5 Correct 1694 ms 15716 KB Output is correct
6 Correct 1699 ms 14460 KB Output is correct
7 Correct 1702 ms 14380 KB Output is correct
8 Correct 1701 ms 15192 KB Output is correct
9 Correct 1693 ms 15076 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1687 ms 14552 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1045 ms 14152 KB Output is correct
4 Correct 1702 ms 15728 KB Output is correct
5 Correct 1694 ms 15716 KB Output is correct
6 Correct 1699 ms 14460 KB Output is correct
7 Correct 1702 ms 14380 KB Output is correct
8 Correct 1701 ms 15192 KB Output is correct
9 Correct 1693 ms 15076 KB Output is correct
10 Correct 1652 ms 12728 KB Output is correct
11 Correct 1654 ms 12712 KB Output is correct
12 Correct 1686 ms 12496 KB Output is correct
13 Correct 1688 ms 12764 KB Output is correct
14 Correct 1680 ms 12768 KB Output is correct
15 Correct 1690 ms 13148 KB Output is correct
16 Correct 1684 ms 15208 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 12136 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1661 ms 12040 KB Output is correct
4 Correct 1699 ms 13536 KB Output is correct
5 Correct 1700 ms 13552 KB Output is correct
6 Correct 1702 ms 12260 KB Output is correct
7 Correct 1698 ms 12156 KB Output is correct
8 Correct 1696 ms 12820 KB Output is correct
9 Correct 1690 ms 12772 KB Output is correct
10 Correct 1688 ms 12516 KB Output is correct
11 Correct 1689 ms 12520 KB Output is correct
12 Correct 1688 ms 12524 KB Output is correct
13 Correct 1687 ms 12512 KB Output is correct
14 Correct 1688 ms 12892 KB Output is correct
15 Correct 1690 ms 12916 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 12136 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1661 ms 12040 KB Output is correct
4 Correct 1699 ms 13536 KB Output is correct
5 Correct 1700 ms 13552 KB Output is correct
6 Correct 1702 ms 12260 KB Output is correct
7 Correct 1698 ms 12156 KB Output is correct
8 Correct 1696 ms 12820 KB Output is correct
9 Correct 1690 ms 12772 KB Output is correct
10 Correct 1688 ms 12516 KB Output is correct
11 Correct 1689 ms 12520 KB Output is correct
12 Correct 1688 ms 12524 KB Output is correct
13 Correct 1687 ms 12512 KB Output is correct
14 Correct 1688 ms 12892 KB Output is correct
15 Correct 1690 ms 12916 KB Output is correct
16 Correct 1974 ms 10880 KB Output is correct
17 Correct 1968 ms 11160 KB Output is correct
18 Correct 1686 ms 10596 KB Output is correct
19 Correct 1683 ms 10588 KB Output is correct
20 Correct 1686 ms 11212 KB Output is correct
21 Correct 1700 ms 10964 KB Output is correct
22 Correct 1690 ms 13180 KB Output is correct
23 Correct 1682 ms 10716 KB Output is correct
24 Correct 1688 ms 10700 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 780 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 780 KB Output is correct
4 Correct 3 ms 900 KB Output is correct
5 Correct 3 ms 900 KB Output is correct
6 Correct 3 ms 908 KB Output is correct
7 Correct 3 ms 904 KB Output is correct
8 Correct 3 ms 908 KB Output is correct
9 Correct 3 ms 900 KB Output is correct
10 Correct 3 ms 900 KB Output is correct
11 Correct 3 ms 900 KB Output is correct
12 Correct 3 ms 864 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 908 KB Output is correct
15 Correct 3 ms 908 KB Output is correct
16 Correct 2 ms 780 KB Output is correct
17 Correct 2 ms 772 KB Output is correct
18 Correct 2 ms 772 KB Output is correct
19 Correct 3 ms 772 KB Output is correct
20 Correct 2 ms 768 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 772 KB Output is correct
23 Incorrect 2 ms 780 KB Wrong Answer [6]
24 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 10388 KB Output is correct
2 Incorrect 1681 ms 10496 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 10432 KB Output is correct
2 Incorrect 1680 ms 10492 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -