oj.uz

Submission #787107

# Submission time Handle Problem Language Result Execution time Memory
787107 2023-07-18T20:22:41 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 2289 ms 16616 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 (A == 2 && i != 0 && graad[i] == 2)
        {
          vi newLijn(lijn);
          newLijn.push_back(j);
          if (graad[V[j]] != 2)
            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 (A == 2 && i != 0 && graad[i] == 2)
        {
          vi newLijn(lijn);
          newLijn.push_back(j);
          if (graad[U[j]] != 2)
            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() < 6)
      continue;
    for (uint32_t i = 0; i < lijn.size(); 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;
}

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 1802 ms 15624 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1209 ms 14828 KB Output is correct
4 Correct 1826 ms 16508 KB Output is correct
5 Correct 1834 ms 16616 KB Output is correct
6 Correct 1837 ms 15200 KB Output is correct
7 Correct 1821 ms 15216 KB Output is correct
8 Correct 1822 ms 15780 KB Output is correct
9 Correct 1807 ms 15952 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1802 ms 15624 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1209 ms 14828 KB Output is correct
4 Correct 1826 ms 16508 KB Output is correct
5 Correct 1834 ms 16616 KB Output is correct
6 Correct 1837 ms 15200 KB Output is correct
7 Correct 1821 ms 15216 KB Output is correct
8 Correct 1822 ms 15780 KB Output is correct
9 Correct 1807 ms 15952 KB Output is correct
10 Correct 1769 ms 13356 KB Output is correct
11 Correct 1751 ms 13388 KB Output is correct
12 Correct 1795 ms 13404 KB Output is correct
13 Correct 1801 ms 13304 KB Output is correct
14 Correct 1801 ms 13484 KB Output is correct
15 Correct 1807 ms 14144 KB Output is correct
16 Correct 1823 ms 16172 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1801 ms 12956 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1762 ms 12656 KB Output is correct
4 Correct 1810 ms 14312 KB Output is correct
5 Correct 1807 ms 14368 KB Output is correct
6 Correct 1794 ms 12912 KB Output is correct
7 Correct 1823 ms 12988 KB Output is correct
8 Correct 1813 ms 13560 KB Output is correct
9 Correct 1813 ms 13476 KB Output is correct
10 Correct 1819 ms 13364 KB Output is correct
11 Correct 1801 ms 13280 KB Output is correct
12 Correct 1823 ms 13260 KB Output is correct
13 Correct 1793 ms 13396 KB Output is correct
14 Correct 1816 ms 13616 KB Output is correct
15 Correct 1838 ms 13696 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1801 ms 12956 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1762 ms 12656 KB Output is correct
4 Correct 1810 ms 14312 KB Output is correct
5 Correct 1807 ms 14368 KB Output is correct
6 Correct 1794 ms 12912 KB Output is correct
7 Correct 1823 ms 12988 KB Output is correct
8 Correct 1813 ms 13560 KB Output is correct
9 Correct 1813 ms 13476 KB Output is correct
10 Correct 1819 ms 13364 KB Output is correct
11 Correct 1801 ms 13280 KB Output is correct
12 Correct 1823 ms 13260 KB Output is correct
13 Correct 1793 ms 13396 KB Output is correct
14 Correct 1816 ms 13616 KB Output is correct
15 Correct 1838 ms 13696 KB Output is correct
16 Correct 2049 ms 11636 KB Output is correct
17 Correct 2057 ms 11720 KB Output is correct
18 Correct 1791 ms 11564 KB Output is correct
19 Correct 1793 ms 11300 KB Output is correct
20 Correct 1807 ms 11960 KB Output is correct
21 Correct 1797 ms 11696 KB Output is correct
22 Correct 1801 ms 13848 KB Output is correct
23 Correct 1821 ms 11452 KB Output is correct
24 Correct 1824 ms 11544 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 900 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 6 ms 908 KB Output is correct
4 Correct 9 ms 904 KB Output is correct
5 Correct 9 ms 908 KB Output is correct
6 Correct 9 ms 908 KB Output is correct
7 Correct 9 ms 904 KB Output is correct
8 Correct 9 ms 908 KB Output is correct
9 Correct 9 ms 908 KB Output is correct
10 Correct 9 ms 960 KB Output is correct
11 Correct 9 ms 880 KB Output is correct
12 Incorrect 19 ms 960 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 2289 ms 13972 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2255 ms 14072 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -