oj.uz

Submission #789428

# Submission time Handle Problem Language Result Execution time Memory
789428 2023-07-21T11:39:23 Z Boas Stray Cat (JOI20_stray) C++17
20 / 100
 235 ms 19092 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(edgeInx);
        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)
      {
        cout << "Infinite loop!";
        throw;
      }
    }
    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 (prevMark == -1)
  {
    for (int i = 0; i < y.size(); i++)
    {
      if ((i != mark && y[i] > 0) || y[i] > 1)
      {
        prevMarks.push_back(i);
      }
    }
  }
  if (A == 2 && (sum == 1 || (prevMark == -1 && sum == 2)))
  {
    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;
}

Compilation message

Catherine.cpp: In function 'int Move(vi)':
Catherine.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < y.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17944 KB Output is correct
2 Correct 1 ms 612 KB Output is correct
3 Correct 45 ms 17768 KB Output is correct
4 Correct 50 ms 19092 KB Output is correct
5 Correct 51 ms 18980 KB Output is correct
6 Correct 45 ms 17684 KB Output is correct
7 Correct 45 ms 17852 KB Output is correct
8 Correct 49 ms 18380 KB Output is correct
9 Correct 55 ms 18408 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17944 KB Output is correct
2 Correct 1 ms 612 KB Output is correct
3 Correct 45 ms 17768 KB Output is correct
4 Correct 50 ms 19092 KB Output is correct
5 Correct 51 ms 18980 KB Output is correct
6 Correct 45 ms 17684 KB Output is correct
7 Correct 45 ms 17852 KB Output is correct
8 Correct 49 ms 18380 KB Output is correct
9 Correct 55 ms 18408 KB Output is correct
10 Correct 44 ms 15872 KB Output is correct
11 Correct 43 ms 15880 KB Output is correct
12 Correct 43 ms 15756 KB Output is correct
13 Correct 47 ms 15804 KB Output is correct
14 Correct 50 ms 16044 KB Output is correct
15 Correct 47 ms 16276 KB Output is correct
16 Correct 51 ms 18548 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15544 KB Output is correct
2 Correct 0 ms 608 KB Output is correct
3 Correct 38 ms 15484 KB Output is correct
4 Correct 59 ms 16876 KB Output is correct
5 Correct 49 ms 16736 KB Output is correct
6 Correct 43 ms 15532 KB Output is correct
7 Correct 42 ms 15568 KB Output is correct
8 Correct 56 ms 16188 KB Output is correct
9 Correct 57 ms 16120 KB Output is correct
10 Correct 46 ms 15880 KB Output is correct
11 Correct 48 ms 15896 KB Output is correct
12 Correct 48 ms 15796 KB Output is correct
13 Correct 45 ms 15996 KB Output is correct
14 Correct 47 ms 16280 KB Output is correct
15 Correct 48 ms 16168 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15544 KB Output is correct
2 Correct 0 ms 608 KB Output is correct
3 Correct 38 ms 15484 KB Output is correct
4 Correct 59 ms 16876 KB Output is correct
5 Correct 49 ms 16736 KB Output is correct
6 Correct 43 ms 15532 KB Output is correct
7 Correct 42 ms 15568 KB Output is correct
8 Correct 56 ms 16188 KB Output is correct
9 Correct 57 ms 16120 KB Output is correct
10 Correct 46 ms 15880 KB Output is correct
11 Correct 48 ms 15896 KB Output is correct
12 Correct 48 ms 15796 KB Output is correct
13 Correct 45 ms 15996 KB Output is correct
14 Correct 47 ms 16280 KB Output is correct
15 Correct 48 ms 16168 KB Output is correct
16 Correct 40 ms 14100 KB Output is correct
17 Correct 40 ms 14128 KB Output is correct
18 Correct 46 ms 13824 KB Output is correct
19 Correct 46 ms 13836 KB Output is correct
20 Correct 45 ms 14452 KB Output is correct
21 Correct 43 ms 14184 KB Output is correct
22 Correct 46 ms 16448 KB Output is correct
23 Correct 41 ms 13896 KB Output is correct
24 Correct 41 ms 13996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 868 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 2 ms 1028 KB Output is correct
5 Correct 3 ms 1008 KB Output is correct
6 Correct 2 ms 1028 KB Output is correct
7 Correct 3 ms 1028 KB Output is correct
8 Correct 2 ms 1028 KB Output is correct
9 Correct 2 ms 1036 KB Output is correct
10 Correct 2 ms 1028 KB Output is correct
11 Correct 2 ms 1036 KB Output is correct
12 Correct 2 ms 904 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 1 ms 1028 KB Output is correct
15 Correct 2 ms 1036 KB Output is correct
16 Correct 2 ms 908 KB Output is correct
17 Correct 2 ms 904 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 2 ms 908 KB Output is correct
21 Correct 2 ms 896 KB Output is correct
22 Correct 2 ms 900 KB Output is correct
23 Correct 2 ms 908 KB Output is correct
24 Correct 2 ms 872 KB Output is correct
25 Correct 2 ms 908 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 952 KB Output is correct
28 Correct 2 ms 912 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13748 KB Output is correct
2 Correct 45 ms 14296 KB Output is correct
3 Correct 0 ms 524 KB Output is correct
4 Correct 37 ms 14096 KB Output is correct
5 Correct 235 ms 15352 KB Output is correct
6 Correct 207 ms 15352 KB Output is correct
7 Correct 230 ms 14384 KB Output is correct
8 Incorrect 196 ms 14336 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13796 KB Output is correct
2 Correct 43 ms 13920 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 38 ms 14112 KB Output is correct
5 Correct 205 ms 15344 KB Output is correct
6 Correct 217 ms 15856 KB Output is correct
7 Correct 217 ms 16480 KB Output is correct
8 Incorrect 199 ms 14328 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -