답안 #789459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789459	2023-07-21T12:11:19 Z	Boas	길고양이 (JOI20_stray)	C++17	100 / 100	1230 ms	23400 KB

Anthony

#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;
}

Catherine

#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)prevMarks.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

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	17872 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	39 ms	17900 KB	Output is correct
4	Correct	50 ms	18996 KB	Output is correct
5	Correct	50 ms	19132 KB	Output is correct
6	Correct	44 ms	17716 KB	Output is correct
7	Correct	45 ms	17716 KB	Output is correct
8	Correct	50 ms	18472 KB	Output is correct
9	Correct	55 ms	18676 KB	Output is correct

Subtask #2

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	17872 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	39 ms	17900 KB	Output is correct
4	Correct	50 ms	18996 KB	Output is correct
5	Correct	50 ms	19132 KB	Output is correct
6	Correct	44 ms	17716 KB	Output is correct
7	Correct	45 ms	17716 KB	Output is correct
8	Correct	50 ms	18472 KB	Output is correct
9	Correct	55 ms	18676 KB	Output is correct
10	Correct	43 ms	15912 KB	Output is correct
11	Correct	44 ms	15836 KB	Output is correct
12	Correct	43 ms	15696 KB	Output is correct
13	Correct	43 ms	15728 KB	Output is correct
14	Correct	43 ms	16064 KB	Output is correct
15	Correct	46 ms	16252 KB	Output is correct
16	Correct	46 ms	18616 KB	Output is correct

Subtask #3

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	15484 KB	Output is correct
2	Correct	1 ms	520 KB	Output is correct
3	Correct	38 ms	15400 KB	Output is correct
4	Correct	49 ms	16864 KB	Output is correct
5	Correct	49 ms	16868 KB	Output is correct
6	Correct	43 ms	15644 KB	Output is correct
7	Correct	43 ms	15564 KB	Output is correct
8	Correct	51 ms	16140 KB	Output is correct
9	Correct	50 ms	16208 KB	Output is correct
10	Correct	49 ms	15888 KB	Output is correct
11	Correct	46 ms	15872 KB	Output is correct
12	Correct	45 ms	15860 KB	Output is correct
13	Correct	45 ms	15936 KB	Output is correct
14	Correct	50 ms	16400 KB	Output is correct
15	Correct	46 ms	16252 KB	Output is correct

Subtask #4

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	15484 KB	Output is correct
2	Correct	1 ms	520 KB	Output is correct
3	Correct	38 ms	15400 KB	Output is correct
4	Correct	49 ms	16864 KB	Output is correct
5	Correct	49 ms	16868 KB	Output is correct
6	Correct	43 ms	15644 KB	Output is correct
7	Correct	43 ms	15564 KB	Output is correct
8	Correct	51 ms	16140 KB	Output is correct
9	Correct	50 ms	16208 KB	Output is correct
10	Correct	49 ms	15888 KB	Output is correct
11	Correct	46 ms	15872 KB	Output is correct
12	Correct	45 ms	15860 KB	Output is correct
13	Correct	45 ms	15936 KB	Output is correct
14	Correct	50 ms	16400 KB	Output is correct
15	Correct	46 ms	16252 KB	Output is correct
16	Correct	40 ms	14192 KB	Output is correct
17	Correct	40 ms	14128 KB	Output is correct
18	Correct	44 ms	13892 KB	Output is correct
19	Correct	40 ms	13844 KB	Output is correct
20	Correct	45 ms	14380 KB	Output is correct
21	Correct	43 ms	14236 KB	Output is correct
22	Correct	45 ms	16368 KB	Output is correct
23	Correct	40 ms	13960 KB	Output is correct
24	Correct	40 ms	13936 KB	Output is correct

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	1 ms	516 KB	Output is correct
3	Correct	1 ms	868 KB	Output is correct
4	Correct	3 ms	1028 KB	Output is correct
5	Correct	2 ms	1032 KB	Output is correct
6	Correct	3 ms	1100 KB	Output is correct
7	Correct	2 ms	1028 KB	Output is correct
8	Correct	2 ms	1032 KB	Output is correct
9	Correct	3 ms	1036 KB	Output is correct
10	Correct	2 ms	1028 KB	Output is correct
11	Correct	2 ms	1032 KB	Output is correct
12	Correct	2 ms	908 KB	Output is correct
13	Correct	2 ms	900 KB	Output is correct
14	Correct	2 ms	1040 KB	Output is correct
15	Correct	2 ms	988 KB	Output is correct
16	Correct	2 ms	908 KB	Output is correct
17	Correct	2 ms	900 KB	Output is correct
18	Correct	2 ms	864 KB	Output is correct
19	Correct	2 ms	972 KB	Output is correct
20	Correct	2 ms	896 KB	Output is correct
21	Correct	2 ms	900 KB	Output is correct
22	Correct	2 ms	908 KB	Output is correct
23	Correct	2 ms	900 KB	Output is correct
24	Correct	2 ms	912 KB	Output is correct
25	Correct	2 ms	908 KB	Output is correct
26	Correct	2 ms	908 KB	Output is correct
27	Correct	2 ms	908 KB	Output is correct
28	Correct	2 ms	908 KB	Output is correct

Subtask #6

71.0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	13908 KB	Output is correct
2	Correct	48 ms	14260 KB	Output is correct
3	Correct	1 ms	520 KB	Output is correct
4	Correct	36 ms	14096 KB	Output is correct
5	Correct	1188 ms	15332 KB	Output is correct
6	Correct	1176 ms	15368 KB	Output is correct
7	Correct	226 ms	23400 KB	Output is correct
8	Correct	198 ms	14340 KB	Output is correct
9	Correct	1190 ms	15276 KB	Output is correct
10	Correct	1199 ms	15548 KB	Output is correct
11	Correct	1230 ms	15356 KB	Output is correct
12	Correct	1182 ms	15608 KB	Output is correct
13	Correct	1210 ms	23248 KB	Output is correct
14	Correct	1196 ms	15376 KB	Output is correct
15	Correct	1158 ms	15372 KB	Output is correct
16	Correct	1167 ms	15312 KB	Output is correct
17	Correct	644 ms	15164 KB	Output is correct
18	Correct	632 ms	14972 KB	Output is correct
19	Correct	623 ms	15020 KB	Output is correct
20	Correct	641 ms	15056 KB	Output is correct
21	Correct	643 ms	15036 KB	Output is correct
22	Correct	671 ms	23152 KB	Output is correct
23	Correct	40 ms	13764 KB	Output is correct
24	Correct	40 ms	13788 KB	Output is correct
25	Correct	55 ms	14100 KB	Output is correct
26	Correct	55 ms	14116 KB	Output is correct
27	Correct	53 ms	14364 KB	Output is correct
28	Correct	45 ms	14292 KB	Output is correct
29	Correct	46 ms	14460 KB	Output is correct
30	Correct	46 ms	14552 KB	Output is correct
31	Correct	40 ms	13820 KB	Output is correct
32	Correct	40 ms	13848 KB	Output is correct
33	Correct	55 ms	14008 KB	Output is correct
34	Correct	57 ms	13908 KB	Output is correct
35	Correct	45 ms	14284 KB	Output is correct
36	Correct	45 ms	14324 KB	Output is correct
37	Correct	45 ms	14284 KB	Output is correct
38	Correct	45 ms	14352 KB	Output is correct
39	Correct	45 ms	14348 KB	Output is correct
40	Correct	45 ms	14300 KB	Output is correct
41	Correct	132 ms	14684 KB	Output is correct
42	Correct	120 ms	14652 KB	Output is correct
43	Correct	120 ms	14736 KB	Output is correct
44	Correct	137 ms	14728 KB	Output is correct
45	Correct	152 ms	14656 KB	Output is correct
46	Correct	138 ms	14788 KB	Output is correct
47	Correct	56 ms	14164 KB	Output is correct
48	Correct	57 ms	14188 KB	Output is correct
49	Correct	47 ms	14160 KB	Output is correct
50	Correct	68 ms	14204 KB	Output is correct
51	Correct	41 ms	14084 KB	Output is correct
52	Correct	43 ms	14068 KB	Output is correct
53	Correct	41 ms	14124 KB	Output is correct
54	Correct	40 ms	14008 KB	Output is correct
55	Correct	41 ms	14056 KB	Output is correct
56	Correct	41 ms	13976 KB	Output is correct
57	Correct	41 ms	13928 KB	Output is correct
58	Correct	43 ms	14008 KB	Output is correct
59	Correct	43 ms	14140 KB	Output is correct
60	Correct	41 ms	14208 KB	Output is correct

Subtask #7

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	13804 KB	Output is correct
2	Correct	44 ms	14020 KB	Output is correct
3	Correct	1 ms	524 KB	Output is correct
4	Correct	41 ms	14132 KB	Output is correct
5	Correct	1171 ms	15320 KB	Output is correct
6	Correct	1167 ms	15372 KB	Output is correct
7	Correct	218 ms	14400 KB	Output is correct
8	Correct	205 ms	14344 KB	Output is correct
9	Correct	1165 ms	15356 KB	Output is correct
10	Correct	1180 ms	15476 KB	Output is correct
11	Correct	1207 ms	15488 KB	Output is correct
12	Correct	1186 ms	15372 KB	Output is correct
13	Correct	1195 ms	15600 KB	Output is correct
14	Correct	1162 ms	15368 KB	Output is correct
15	Correct	1177 ms	19588 KB	Output is correct
16	Correct	1161 ms	15352 KB	Output is correct
17	Correct	652 ms	15064 KB	Output is correct
18	Correct	641 ms	21400 KB	Output is correct
19	Correct	634 ms	14992 KB	Output is correct
20	Correct	642 ms	15068 KB	Output is correct
21	Correct	633 ms	15048 KB	Output is correct
22	Correct	643 ms	15292 KB	Output is correct
23	Correct	41 ms	13760 KB	Output is correct
24	Correct	41 ms	13708 KB	Output is correct
25	Correct	55 ms	14028 KB	Output is correct
26	Correct	55 ms	14008 KB	Output is correct
27	Correct	47 ms	14324 KB	Output is correct
28	Correct	55 ms	14428 KB	Output is correct
29	Correct	47 ms	14380 KB	Output is correct
30	Correct	47 ms	14484 KB	Output is correct
31	Correct	41 ms	13768 KB	Output is correct
32	Correct	41 ms	13776 KB	Output is correct
33	Correct	56 ms	14068 KB	Output is correct
34	Correct	60 ms	14048 KB	Output is correct
35	Correct	46 ms	14328 KB	Output is correct
36	Correct	46 ms	14276 KB	Output is correct
37	Correct	47 ms	14280 KB	Output is correct
38	Correct	47 ms	14288 KB	Output is correct
39	Correct	46 ms	14340 KB	Output is correct
40	Correct	46 ms	14292 KB	Output is correct
41	Correct	120 ms	14700 KB	Output is correct
42	Correct	126 ms	14708 KB	Output is correct
43	Correct	121 ms	14668 KB	Output is correct
44	Correct	135 ms	14788 KB	Output is correct
45	Correct	148 ms	15032 KB	Output is correct
46	Correct	140 ms	14740 KB	Output is correct
47	Correct	57 ms	14268 KB	Output is correct
48	Correct	56 ms	14268 KB	Output is correct
49	Correct	46 ms	14148 KB	Output is correct
50	Correct	67 ms	14260 KB	Output is correct
51	Correct	43 ms	14028 KB	Output is correct
52	Correct	43 ms	14044 KB	Output is correct
53	Correct	44 ms	14068 KB	Output is correct
54	Correct	43 ms	13956 KB	Output is correct
55	Correct	41 ms	13932 KB	Output is correct
56	Correct	49 ms	14060 KB	Output is correct
57	Correct	44 ms	14000 KB	Output is correct
58	Correct	41 ms	14036 KB	Output is correct
59	Correct	44 ms	14064 KB	Output is correct
60	Correct	44 ms	14044 KB	Output is correct