oj.uz

Submission #788999

# Submission time Handle Problem Language Result Execution time Memory
788999 2023-07-20T20:09:47 Z Boas Stray Cat (JOI20_stray) C++17
91 / 100
 250 ms 22592 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)
  {
    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 45 ms 17988 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 40 ms 17908 KB Output is correct
4 Correct 53 ms 19080 KB Output is correct
5 Correct 54 ms 19084 KB Output is correct
6 Correct 43 ms 17676 KB Output is correct
7 Correct 45 ms 17776 KB Output is correct
8 Correct 49 ms 18384 KB Output is correct
9 Correct 48 ms 18488 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17988 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 40 ms 17908 KB Output is correct
4 Correct 53 ms 19080 KB Output is correct
5 Correct 54 ms 19084 KB Output is correct
6 Correct 43 ms 17676 KB Output is correct
7 Correct 45 ms 17776 KB Output is correct
8 Correct 49 ms 18384 KB Output is correct
9 Correct 48 ms 18488 KB Output is correct
10 Correct 53 ms 15760 KB Output is correct
11 Correct 47 ms 15884 KB Output is correct
12 Correct 46 ms 15704 KB Output is correct
13 Correct 41 ms 15748 KB Output is correct
14 Correct 43 ms 15880 KB Output is correct
15 Correct 46 ms 16348 KB Output is correct
16 Correct 47 ms 18516 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15516 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 39 ms 15480 KB Output is correct
4 Correct 50 ms 16856 KB Output is correct
5 Correct 55 ms 16884 KB Output is correct
6 Correct 43 ms 15500 KB Output is correct
7 Correct 42 ms 15724 KB Output is correct
8 Correct 51 ms 16076 KB Output is correct
9 Correct 53 ms 16320 KB Output is correct
10 Correct 55 ms 15792 KB Output is correct
11 Correct 51 ms 15900 KB Output is correct
12 Correct 46 ms 15888 KB Output is correct
13 Correct 45 ms 15944 KB Output is correct
14 Correct 47 ms 16260 KB Output is correct
15 Correct 48 ms 16236 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15516 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 39 ms 15480 KB Output is correct
4 Correct 50 ms 16856 KB Output is correct
5 Correct 55 ms 16884 KB Output is correct
6 Correct 43 ms 15500 KB Output is correct
7 Correct 42 ms 15724 KB Output is correct
8 Correct 51 ms 16076 KB Output is correct
9 Correct 53 ms 16320 KB Output is correct
10 Correct 55 ms 15792 KB Output is correct
11 Correct 51 ms 15900 KB Output is correct
12 Correct 46 ms 15888 KB Output is correct
13 Correct 45 ms 15944 KB Output is correct
14 Correct 47 ms 16260 KB Output is correct
15 Correct 48 ms 16236 KB Output is correct
16 Correct 41 ms 14188 KB Output is correct
17 Correct 44 ms 14144 KB Output is correct
18 Correct 40 ms 13876 KB Output is correct
19 Correct 43 ms 13864 KB Output is correct
20 Correct 45 ms 14448 KB Output is correct
21 Correct 43 ms 14092 KB Output is correct
22 Correct 45 ms 16412 KB Output is correct
23 Correct 41 ms 13932 KB Output is correct
24 Correct 41 ms 14004 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 908 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1 ms 900 KB Output is correct
4 Correct 2 ms 1028 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 2 ms 1036 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 2 ms 1036 KB Output is correct
9 Correct 2 ms 1028 KB Output is correct
10 Correct 2 ms 1028 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 908 KB Output is correct
14 Correct 2 ms 1044 KB Output is correct
15 Correct 2 ms 1028 KB Output is correct
16 Correct 2 ms 908 KB Output is correct
17 Correct 2 ms 908 KB Output is correct
18 Correct 2 ms 864 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 900 KB Output is correct
21 Correct 2 ms 900 KB Output is correct
22 Correct 2 ms 900 KB Output is correct
23 Correct 2 ms 900 KB Output is correct
24 Correct 2 ms 900 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 2 ms 900 KB Output is correct
27 Correct 2 ms 904 KB Output is correct
28 Correct 2 ms 900 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13756 KB Output is correct
2 Correct 45 ms 14104 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 38 ms 14108 KB Output is correct
5 Correct 212 ms 15356 KB Output is correct
6 Correct 208 ms 15360 KB Output is correct
7 Correct 213 ms 14588 KB Output is correct
8 Correct 197 ms 14344 KB Output is correct
9 Correct 215 ms 21756 KB Output is correct
10 Correct 211 ms 15356 KB Output is correct
11 Correct 205 ms 15312 KB Output is correct
12 Correct 206 ms 15356 KB Output is correct
13 Correct 219 ms 22592 KB Output is correct
14 Correct 208 ms 15356 KB Output is correct
15 Correct 250 ms 15352 KB Output is correct
16 Correct 217 ms 15460 KB Output is correct
17 Correct 208 ms 14956 KB Output is correct
18 Correct 201 ms 14980 KB Output is correct
19 Correct 214 ms 15220 KB Output is correct
20 Correct 204 ms 14988 KB Output is correct
21 Correct 205 ms 14968 KB Output is correct
22 Correct 216 ms 15320 KB Output is correct
23 Correct 47 ms 13892 KB Output is correct
24 Correct 40 ms 13800 KB Output is correct
25 Correct 45 ms 14020 KB Output is correct
26 Correct 46 ms 14100 KB Output is correct
27 Correct 46 ms 14320 KB Output is correct
28 Correct 46 ms 14316 KB Output is correct
29 Correct 46 ms 14360 KB Output is correct
30 Correct 46 ms 14444 KB Output is correct
31 Correct 41 ms 13768 KB Output is correct
32 Correct 41 ms 13848 KB Output is correct
33 Correct 46 ms 13908 KB Output is correct
34 Correct 46 ms 14004 KB Output is correct
35 Correct 45 ms 14256 KB Output is correct
36 Correct 46 ms 14356 KB Output is correct
37 Correct 52 ms 14352 KB Output is correct
38 Correct 53 ms 14300 KB Output is correct
39 Correct 47 ms 14384 KB Output is correct
40 Correct 47 ms 14424 KB Output is correct
41 Correct 62 ms 14648 KB Output is correct
42 Correct 56 ms 14732 KB Output is correct
43 Correct 53 ms 14696 KB Output is correct
44 Correct 53 ms 14788 KB Output is correct
45 Correct 54 ms 14860 KB Output is correct
46 Correct 63 ms 14744 KB Output is correct
47 Correct 49 ms 14276 KB Output is correct
48 Correct 47 ms 14276 KB Output is correct
49 Correct 48 ms 14116 KB Output is correct
50 Correct 47 ms 14384 KB Output is correct
51 Correct 45 ms 13960 KB Output is correct
52 Correct 44 ms 14196 KB Output is correct
53 Correct 43 ms 13956 KB Output is correct
54 Correct 44 ms 13996 KB Output is correct
55 Correct 43 ms 13940 KB Output is correct
56 Correct 49 ms 13980 KB Output is correct
57 Correct 44 ms 13988 KB Output is correct
58 Correct 43 ms 13924 KB Output is correct
59 Correct 47 ms 14228 KB Output is correct
60 Correct 44 ms 14132 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13768 KB Output is correct
2 Correct 44 ms 14008 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 38 ms 14060 KB Output is correct
5 Correct 209 ms 15364 KB Output is correct
6 Correct 220 ms 16672 KB Output is correct
7 Incorrect 198 ms 13900 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -