oj.uz

Submission #788921

# Submission time Handle Problem Language Result Execution time Memory
788921 2023-07-20T17:29:25 Z Boas Stray Cat (JOI20_stray) C++17
91 / 100
 254 ms 18672 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)
      {
        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 54 ms 17560 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 40 ms 17576 KB Output is correct
4 Correct 52 ms 18632 KB Output is correct
5 Correct 50 ms 18672 KB Output is correct
6 Correct 45 ms 17392 KB Output is correct
7 Correct 51 ms 17368 KB Output is correct
8 Correct 48 ms 18028 KB Output is correct
9 Correct 49 ms 17940 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 17560 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 40 ms 17576 KB Output is correct
4 Correct 52 ms 18632 KB Output is correct
5 Correct 50 ms 18672 KB Output is correct
6 Correct 45 ms 17392 KB Output is correct
7 Correct 51 ms 17368 KB Output is correct
8 Correct 48 ms 18028 KB Output is correct
9 Correct 49 ms 17940 KB Output is correct
10 Correct 41 ms 15512 KB Output is correct
11 Correct 45 ms 15356 KB Output is correct
12 Correct 44 ms 15348 KB Output is correct
13 Correct 43 ms 15296 KB Output is correct
14 Correct 45 ms 15532 KB Output is correct
15 Correct 52 ms 15792 KB Output is correct
16 Correct 54 ms 18184 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15072 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 38 ms 14928 KB Output is correct
4 Correct 51 ms 16404 KB Output is correct
5 Correct 50 ms 16436 KB Output is correct
6 Correct 42 ms 15100 KB Output is correct
7 Correct 44 ms 15204 KB Output is correct
8 Correct 48 ms 15724 KB Output is correct
9 Correct 49 ms 15856 KB Output is correct
10 Correct 56 ms 15512 KB Output is correct
11 Correct 53 ms 15496 KB Output is correct
12 Correct 47 ms 15384 KB Output is correct
13 Correct 44 ms 15440 KB Output is correct
14 Correct 47 ms 15712 KB Output is correct
15 Correct 47 ms 15872 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15072 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 38 ms 14928 KB Output is correct
4 Correct 51 ms 16404 KB Output is correct
5 Correct 50 ms 16436 KB Output is correct
6 Correct 42 ms 15100 KB Output is correct
7 Correct 44 ms 15204 KB Output is correct
8 Correct 48 ms 15724 KB Output is correct
9 Correct 49 ms 15856 KB Output is correct
10 Correct 56 ms 15512 KB Output is correct
11 Correct 53 ms 15496 KB Output is correct
12 Correct 47 ms 15384 KB Output is correct
13 Correct 44 ms 15440 KB Output is correct
14 Correct 47 ms 15712 KB Output is correct
15 Correct 47 ms 15872 KB Output is correct
16 Correct 41 ms 13792 KB Output is correct
17 Correct 40 ms 13720 KB Output is correct
18 Correct 45 ms 13488 KB Output is correct
19 Correct 40 ms 13336 KB Output is correct
20 Correct 45 ms 13924 KB Output is correct
21 Correct 43 ms 13792 KB Output is correct
22 Correct 45 ms 16100 KB Output is correct
23 Correct 50 ms 13448 KB Output is correct
24 Correct 41 ms 13532 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 1032 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 2 ms 992 KB Output is correct
7 Correct 2 ms 1036 KB Output is correct
8 Correct 2 ms 1032 KB Output is correct
9 Correct 2 ms 988 KB Output is correct
10 Correct 2 ms 1036 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 2 ms 1036 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 1036 KB Output is correct
15 Correct 2 ms 1036 KB Output is correct
16 Correct 2 ms 912 KB Output is correct
17 Correct 2 ms 900 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 908 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 904 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 3 ms 900 KB Output is correct
25 Correct 3 ms 908 KB Output is correct
26 Correct 2 ms 908 KB Output is correct
27 Correct 2 ms 900 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 45 ms 13436 KB Output is correct
2 Correct 45 ms 14244 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Correct 42 ms 14068 KB Output is correct
5 Correct 208 ms 15352 KB Output is correct
6 Correct 229 ms 15340 KB Output is correct
7 Correct 212 ms 18428 KB Output is correct
8 Correct 203 ms 14332 KB Output is correct
9 Correct 216 ms 15472 KB Output is correct
10 Correct 224 ms 15396 KB Output is correct
11 Correct 218 ms 15360 KB Output is correct
12 Correct 217 ms 15364 KB Output is correct
13 Correct 217 ms 15380 KB Output is correct
14 Correct 247 ms 15344 KB Output is correct
15 Correct 213 ms 15360 KB Output is correct
16 Correct 219 ms 15348 KB Output is correct
17 Correct 210 ms 14968 KB Output is correct
18 Correct 222 ms 15224 KB Output is correct
19 Correct 229 ms 15096 KB Output is correct
20 Correct 207 ms 15020 KB Output is correct
21 Correct 222 ms 14984 KB Output is correct
22 Correct 208 ms 14976 KB Output is correct
23 Correct 41 ms 13760 KB Output is correct
24 Correct 47 ms 13840 KB Output is correct
25 Correct 55 ms 14004 KB Output is correct
26 Correct 47 ms 13980 KB Output is correct
27 Correct 47 ms 14464 KB Output is correct
28 Correct 52 ms 14420 KB Output is correct
29 Correct 55 ms 14416 KB Output is correct
30 Correct 48 ms 14368 KB Output is correct
31 Correct 50 ms 13812 KB Output is correct
32 Correct 45 ms 13812 KB Output is correct
33 Correct 45 ms 14028 KB Output is correct
34 Correct 49 ms 13960 KB Output is correct
35 Correct 47 ms 14348 KB Output is correct
36 Correct 49 ms 14352 KB Output is correct
37 Correct 46 ms 14252 KB Output is correct
38 Correct 53 ms 14284 KB Output is correct
39 Correct 46 ms 14324 KB Output is correct
40 Correct 54 ms 14268 KB Output is correct
41 Correct 60 ms 14692 KB Output is correct
42 Correct 54 ms 14756 KB Output is correct
43 Correct 80 ms 14664 KB Output is correct
44 Correct 56 ms 14896 KB Output is correct
45 Correct 57 ms 14780 KB Output is correct
46 Correct 57 ms 14800 KB Output is correct
47 Correct 49 ms 14228 KB Output is correct
48 Correct 49 ms 14264 KB Output is correct
49 Correct 45 ms 14140 KB Output is correct
50 Correct 63 ms 14212 KB Output is correct
51 Correct 49 ms 13868 KB Output is correct
52 Correct 43 ms 13992 KB Output is correct
53 Correct 48 ms 14052 KB Output is correct
54 Correct 46 ms 14020 KB Output is correct
55 Correct 55 ms 13992 KB Output is correct
56 Correct 45 ms 14104 KB Output is correct
57 Correct 50 ms 14024 KB Output is correct
58 Correct 44 ms 14012 KB Output is correct
59 Correct 43 ms 14184 KB Output is correct
60 Correct 43 ms 14108 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13784 KB Output is correct
2 Correct 45 ms 14096 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 37 ms 14072 KB Output is correct
5 Correct 232 ms 15352 KB Output is correct
6 Correct 218 ms 15352 KB Output is correct
7 Incorrect 254 ms 14324 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -