oj.uz

Submission #787177

# Submission time Handle Problem Language Result Execution time Memory
787177 2023-07-18T22:32:46 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 2054 ms 16052 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 1835 ms 14860 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 1216 ms 14492 KB Output is correct
4 Correct 1825 ms 16016 KB Output is correct
5 Correct 1820 ms 16052 KB Output is correct
6 Correct 1839 ms 14724 KB Output is correct
7 Correct 1819 ms 14720 KB Output is correct
8 Correct 1865 ms 15416 KB Output is correct
9 Correct 1822 ms 15472 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1835 ms 14860 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 1216 ms 14492 KB Output is correct
4 Correct 1825 ms 16016 KB Output is correct
5 Correct 1820 ms 16052 KB Output is correct
6 Correct 1839 ms 14724 KB Output is correct
7 Correct 1819 ms 14720 KB Output is correct
8 Correct 1865 ms 15416 KB Output is correct
9 Correct 1822 ms 15472 KB Output is correct
10 Correct 1788 ms 12952 KB Output is correct
11 Correct 1768 ms 12916 KB Output is correct
12 Correct 1817 ms 12928 KB Output is correct
13 Correct 1827 ms 12816 KB Output is correct
14 Correct 1811 ms 13024 KB Output is correct
15 Correct 1815 ms 13420 KB Output is correct
16 Correct 1821 ms 15516 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1817 ms 12448 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1744 ms 12268 KB Output is correct
4 Correct 1873 ms 13936 KB Output is correct
5 Correct 1830 ms 13948 KB Output is correct
6 Correct 1831 ms 12508 KB Output is correct
7 Correct 1823 ms 12504 KB Output is correct
8 Correct 1821 ms 13192 KB Output is correct
9 Correct 1816 ms 13068 KB Output is correct
10 Correct 1814 ms 12928 KB Output is correct
11 Correct 1817 ms 12828 KB Output is correct
12 Correct 1825 ms 12904 KB Output is correct
13 Correct 1813 ms 12956 KB Output is correct
14 Correct 1838 ms 13320 KB Output is correct
15 Correct 1833 ms 13180 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1817 ms 12448 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1744 ms 12268 KB Output is correct
4 Correct 1873 ms 13936 KB Output is correct
5 Correct 1830 ms 13948 KB Output is correct
6 Correct 1831 ms 12508 KB Output is correct
7 Correct 1823 ms 12504 KB Output is correct
8 Correct 1821 ms 13192 KB Output is correct
9 Correct 1816 ms 13068 KB Output is correct
10 Correct 1814 ms 12928 KB Output is correct
11 Correct 1817 ms 12828 KB Output is correct
12 Correct 1825 ms 12904 KB Output is correct
13 Correct 1813 ms 12956 KB Output is correct
14 Correct 1838 ms 13320 KB Output is correct
15 Correct 1833 ms 13180 KB Output is correct
16 Correct 2053 ms 11348 KB Output is correct
17 Correct 2054 ms 11144 KB Output is correct
18 Correct 1815 ms 10968 KB Output is correct
19 Correct 1841 ms 10956 KB Output is correct
20 Correct 1827 ms 11508 KB Output is correct
21 Correct 1829 ms 11252 KB Output is correct
22 Correct 1849 ms 13480 KB Output is correct
23 Correct 1831 ms 11024 KB Output is correct
24 Correct 1824 ms 10992 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 904 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 9 ms 972 KB Output is correct
5 Correct 9 ms 936 KB Output is correct
6 Correct 12 ms 904 KB Output is correct
7 Correct 9 ms 968 KB Output is correct
8 Correct 9 ms 896 KB Output is correct
9 Correct 9 ms 952 KB Output is correct
10 Correct 13 ms 1052 KB Output is correct
11 Correct 11 ms 896 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 9 ms 900 KB Output is correct
14 Correct 9 ms 904 KB Output is correct
15 Correct 9 ms 836 KB Output is correct
16 Incorrect 7 ms 908 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1840 ms 10940 KB Output is correct
2 Incorrect 1862 ms 11780 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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