oj.uz

Submission #788919

# Submission time Handle Problem Language Result Execution time Memory
788919 2023-07-20T17:26:24 Z Boas Stray Cat (JOI20_stray) C++17
15 / 100
 59 ms 19116 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

namespace
{
  int a, m;
  bool debug = false;
}

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef pair<int,int> pii;

void setDebug(bool v)
{
  debug = v;
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V)
{
  a = A;
  m = M;
  vvi adj(N);
  vector<int> graad(N);
  map<pii, int> edgeIndex;
  for (int i = 0; i < m; i++)
  {
    int a = U[i], b = V[i];
    adj[a].push_back(b);
    adj[b].push_back(a);
    graad[a]++;
    graad[b]++;
    edgeIndex[{a, b}] = i;
    edgeIndex[{b, a}] = i;
  }
  vector<int> X(M, -1);
  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();
    bool isEnd = true;
    for (int j : adj[i])
    {
      int edgeInx = edgeIndex[{i, j}];
      if (X[edgeInx] != -1)
        continue;
      isEnd = false;
      if (debug)
        cerr << "Road from " << i << " to " << j << " gets mark " << mark << endl;
      X[edgeInx] = mark;
      if (a == 2 && graad[i] != 2)
      {
        if (lijn.size() >= 4)
        {
          lijnen.push_back(lijn);
        }
        lijn.clear();
      }
      if (a != 2 || (graad[i] != 2 && graad[j] != 2))
      {
        q.push({j, (mark - 1 + a) % a, lijn});
      }
      else
      {
        vi newLijn(lijn);
        newLijn.push_back(j);
        q.push({j, (mark - 1 + a) % a, newLijn});
      }
    }
    if (A == 2 && isEnd && lijn.size() >= 4)
      lijnen.push_back(lijn);
  }
  vi pattern = {0, 0, 1, 0, 1, 1};
  for (const auto &lijn : lijnen)
  {
    if (lijn.size() < 4)
      continue;
    int d = 0;
    while (X[lijn[0]] != pattern[(d) % 6] || X[lijn.back()] != pattern[(d + lijn.size() - 1) % 6])
    {
      d++;
      if (d > 1000)
      {
        break;
      }
    }
    for (uint32_t i = 0; i < lijn.size(); i++)
    {
      int mark = pattern[(i + d) % 6];
      if (debug)
        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 46 ms 17920 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 40 ms 17816 KB Output is correct
4 Correct 52 ms 19088 KB Output is correct
5 Correct 56 ms 19116 KB Output is correct
6 Correct 45 ms 17788 KB Output is correct
7 Correct 45 ms 17652 KB Output is correct
8 Correct 49 ms 18412 KB Output is correct
9 Correct 51 ms 18456 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17920 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 40 ms 17816 KB Output is correct
4 Correct 52 ms 19088 KB Output is correct
5 Correct 56 ms 19116 KB Output is correct
6 Correct 45 ms 17788 KB Output is correct
7 Correct 45 ms 17652 KB Output is correct
8 Correct 49 ms 18412 KB Output is correct
9 Correct 51 ms 18456 KB Output is correct
10 Correct 43 ms 15824 KB Output is correct
11 Correct 43 ms 15812 KB Output is correct
12 Correct 44 ms 15760 KB Output is correct
13 Correct 40 ms 15760 KB Output is correct
14 Correct 43 ms 15944 KB Output is correct
15 Correct 46 ms 16300 KB Output is correct
16 Correct 58 ms 18572 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15488 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 38 ms 15388 KB Output is correct
4 Correct 51 ms 16768 KB Output is correct
5 Correct 59 ms 16880 KB Output is correct
6 Correct 43 ms 15552 KB Output is correct
7 Correct 47 ms 15508 KB Output is correct
8 Correct 48 ms 16208 KB Output is correct
9 Correct 47 ms 16184 KB Output is correct
10 Correct 46 ms 16044 KB Output is correct
11 Correct 44 ms 15948 KB Output is correct
12 Correct 47 ms 15828 KB Output is correct
13 Correct 52 ms 15844 KB Output is correct
14 Correct 47 ms 16264 KB Output is correct
15 Correct 50 ms 16276 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15488 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 38 ms 15388 KB Output is correct
4 Correct 51 ms 16768 KB Output is correct
5 Correct 59 ms 16880 KB Output is correct
6 Correct 43 ms 15552 KB Output is correct
7 Correct 47 ms 15508 KB Output is correct
8 Correct 48 ms 16208 KB Output is correct
9 Correct 47 ms 16184 KB Output is correct
10 Correct 46 ms 16044 KB Output is correct
11 Correct 44 ms 15948 KB Output is correct
12 Correct 47 ms 15828 KB Output is correct
13 Correct 52 ms 15844 KB Output is correct
14 Correct 47 ms 16264 KB Output is correct
15 Correct 50 ms 16276 KB Output is correct
16 Correct 50 ms 14196 KB Output is correct
17 Correct 40 ms 14100 KB Output is correct
18 Correct 46 ms 13772 KB Output is correct
19 Correct 48 ms 13872 KB Output is correct
20 Correct 44 ms 14388 KB Output is correct
21 Correct 43 ms 14200 KB Output is correct
22 Correct 46 ms 16444 KB Output is correct
23 Correct 41 ms 13952 KB Output is correct
24 Correct 49 ms 14028 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 2 ms 908 KB Output is correct
4 Runtime error 1 ms 724 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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