oj.uz

Submission #788098

# Submission time Handle Problem Language Result Execution time Memory
788098 2023-07-19T18:28:16 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 2079 ms 16516 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)
          {
            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() < 4)
      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;
  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 1853 ms 15364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1206 ms 14832 KB Output is correct
4 Correct 1890 ms 16488 KB Output is correct
5 Correct 1872 ms 16516 KB Output is correct
6 Correct 1828 ms 15120 KB Output is correct
7 Correct 1873 ms 15228 KB Output is correct
8 Correct 1811 ms 15844 KB Output is correct
9 Correct 1847 ms 15820 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 15364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1206 ms 14832 KB Output is correct
4 Correct 1890 ms 16488 KB Output is correct
5 Correct 1872 ms 16516 KB Output is correct
6 Correct 1828 ms 15120 KB Output is correct
7 Correct 1873 ms 15228 KB Output is correct
8 Correct 1811 ms 15844 KB Output is correct
9 Correct 1847 ms 15820 KB Output is correct
10 Correct 1813 ms 13568 KB Output is correct
11 Correct 1781 ms 13344 KB Output is correct
12 Correct 1813 ms 13132 KB Output is correct
13 Correct 1833 ms 13236 KB Output is correct
14 Correct 1817 ms 13568 KB Output is correct
15 Correct 1839 ms 13972 KB Output is correct
16 Correct 1829 ms 15904 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1817 ms 12944 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1789 ms 12704 KB Output is correct
4 Correct 1814 ms 14244 KB Output is correct
5 Correct 1839 ms 14356 KB Output is correct
6 Correct 1821 ms 13092 KB Output is correct
7 Correct 1824 ms 13088 KB Output is correct
8 Correct 1835 ms 13556 KB Output is correct
9 Correct 1827 ms 13500 KB Output is correct
10 Correct 1833 ms 13324 KB Output is correct
11 Correct 1829 ms 13400 KB Output is correct
12 Correct 1833 ms 13328 KB Output is correct
13 Correct 1820 ms 13392 KB Output is correct
14 Correct 1839 ms 13720 KB Output is correct
15 Correct 1843 ms 13688 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1817 ms 12944 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1789 ms 12704 KB Output is correct
4 Correct 1814 ms 14244 KB Output is correct
5 Correct 1839 ms 14356 KB Output is correct
6 Correct 1821 ms 13092 KB Output is correct
7 Correct 1824 ms 13088 KB Output is correct
8 Correct 1835 ms 13556 KB Output is correct
9 Correct 1827 ms 13500 KB Output is correct
10 Correct 1833 ms 13324 KB Output is correct
11 Correct 1829 ms 13400 KB Output is correct
12 Correct 1833 ms 13328 KB Output is correct
13 Correct 1820 ms 13392 KB Output is correct
14 Correct 1839 ms 13720 KB Output is correct
15 Correct 1843 ms 13688 KB Output is correct
16 Correct 2079 ms 11588 KB Output is correct
17 Correct 2045 ms 11628 KB Output is correct
18 Correct 1811 ms 11356 KB Output is correct
19 Correct 1813 ms 11284 KB Output is correct
20 Correct 1861 ms 11956 KB Output is correct
21 Correct 1837 ms 11620 KB Output is correct
22 Correct 1868 ms 13924 KB Output is correct
23 Correct 1831 ms 11468 KB Output is correct
24 Correct 1853 ms 11592 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 524 KB Output is correct
3 Correct 6 ms 868 KB Output is correct
4 Correct 9 ms 908 KB Output is correct
5 Correct 12 ms 880 KB Output is correct
6 Correct 9 ms 900 KB Output is correct
7 Correct 9 ms 908 KB Output is correct
8 Correct 9 ms 944 KB Output is correct
9 Correct 9 ms 900 KB Output is correct
10 Correct 9 ms 984 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 8 ms 960 KB Output is correct
13 Correct 9 ms 900 KB Output is correct
14 Correct 9 ms 908 KB Output is correct
15 Correct 9 ms 904 KB Output is correct
16 Incorrect 6 ms 900 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1837 ms 11472 KB Output is correct
2 Incorrect 1932 ms 11696 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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