oj.uz

Submission #787157

# Submission time Handle Problem Language Result Execution time Memory
787157 2023-07-18T21:34:53 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 2240 ms 16572 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;
  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 1829 ms 15400 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1216 ms 14916 KB Output is correct
4 Correct 1805 ms 16556 KB Output is correct
5 Correct 1827 ms 16572 KB Output is correct
6 Correct 1819 ms 15092 KB Output is correct
7 Correct 1837 ms 15040 KB Output is correct
8 Correct 1833 ms 15836 KB Output is correct
9 Correct 1829 ms 15784 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1829 ms 15400 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 1216 ms 14916 KB Output is correct
4 Correct 1805 ms 16556 KB Output is correct
5 Correct 1827 ms 16572 KB Output is correct
6 Correct 1819 ms 15092 KB Output is correct
7 Correct 1837 ms 15040 KB Output is correct
8 Correct 1833 ms 15836 KB Output is correct
9 Correct 1829 ms 15784 KB Output is correct
10 Correct 1751 ms 13372 KB Output is correct
11 Correct 1783 ms 13492 KB Output is correct
12 Correct 1833 ms 13328 KB Output is correct
13 Correct 1836 ms 13332 KB Output is correct
14 Correct 1811 ms 13580 KB Output is correct
15 Correct 1806 ms 13852 KB Output is correct
16 Correct 1825 ms 16024 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 12936 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1797 ms 12688 KB Output is correct
4 Correct 1811 ms 14508 KB Output is correct
5 Correct 1815 ms 14340 KB Output is correct
6 Correct 1814 ms 13000 KB Output is correct
7 Correct 1799 ms 12984 KB Output is correct
8 Correct 1803 ms 13504 KB Output is correct
9 Correct 1809 ms 13496 KB Output is correct
10 Correct 1817 ms 13360 KB Output is correct
11 Correct 1795 ms 13324 KB Output is correct
12 Correct 1793 ms 13312 KB Output is correct
13 Correct 1791 ms 13232 KB Output is correct
14 Correct 1787 ms 13696 KB Output is correct
15 Correct 1803 ms 13572 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 12936 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1797 ms 12688 KB Output is correct
4 Correct 1811 ms 14508 KB Output is correct
5 Correct 1815 ms 14340 KB Output is correct
6 Correct 1814 ms 13000 KB Output is correct
7 Correct 1799 ms 12984 KB Output is correct
8 Correct 1803 ms 13504 KB Output is correct
9 Correct 1809 ms 13496 KB Output is correct
10 Correct 1817 ms 13360 KB Output is correct
11 Correct 1795 ms 13324 KB Output is correct
12 Correct 1793 ms 13312 KB Output is correct
13 Correct 1791 ms 13232 KB Output is correct
14 Correct 1787 ms 13696 KB Output is correct
15 Correct 1803 ms 13572 KB Output is correct
16 Correct 2036 ms 11620 KB Output is correct
17 Correct 2032 ms 11684 KB Output is correct
18 Correct 1790 ms 11368 KB Output is correct
19 Correct 1789 ms 11396 KB Output is correct
20 Correct 1811 ms 11984 KB Output is correct
21 Correct 1791 ms 11768 KB Output is correct
22 Correct 1819 ms 13900 KB Output is correct
23 Correct 1805 ms 11516 KB Output is correct
24 Correct 1803 ms 11384 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 932 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 9 ms 972 KB Output is correct
5 Correct 9 ms 916 KB Output is correct
6 Correct 9 ms 984 KB Output is correct
7 Correct 12 ms 1140 KB Output is correct
8 Correct 9 ms 988 KB Output is correct
9 Correct 9 ms 900 KB Output is correct
10 Correct 9 ms 992 KB Output is correct
11 Correct 9 ms 908 KB Output is correct
12 Incorrect 20 ms 1000 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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