#include "Anthony.h"
#include <bits/stdc++.h>
namespace
{
int a, m;
}
using namespace std;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V)
{
a = A;
m = M;
vector<int> X(M, -1);
vector<int> graad(N);
for (int i : U)
graad[i]++;
for (int i : V)
graad[i]++;
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();
for (int j = 0; j < m; j++)
{
if (X[j] != -1)
continue;
if (U[j] == i)
{
// cerr << "Road from " << i << " to " << V[j] << " gets mark " << mark << endl;
X[j] = mark;
if (graad[i] != 2)
lijn.clear();
if (A == 2 && i != 0 && graad[i] == 2)
{
vi newLijn(lijn);
newLijn.push_back(j);
if (graad[V[j]] != 2 && newLijn.size() > 3)
{
lijnen.push_back(newLijn);
}
q.push({V[j], (mark - 1 + a) % a, newLijn});
}
else
q.push({V[j], (mark - 1 + a) % a, lijn});
}
else if (V[j] == i)
{
// cerr << "Road from " << i << " to " << U[j] << " gets mark " << mark << endl;
X[j] = mark;
if (graad[i] != 2)
lijn.clear();
if (A == 2 && i != 0 && graad[i] == 2)
{
vi newLijn(lijn);
newLijn.push_back(j);
if (graad[U[j]] != 2 && newLijn.size() > 3)
{
lijnen.push_back(newLijn);
}
q.push({U[j], (mark - 1 + a) % a, newLijn});
}
else
q.push({U[j], (mark - 1 + a) % a, lijn});
}
}
}
vi pattern = {0, 0, 1, 0, 1, 1};
for (const auto &lijn : lijnen)
{
if (lijn.size() < 4)
continue;
for (uint32_t i = 1; i < lijn.size() - 1; i++)
{
int mark = pattern[i % 6];
// 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1687 ms |
14552 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1045 ms |
14152 KB |
Output is correct |
4 |
Correct |
1702 ms |
15728 KB |
Output is correct |
5 |
Correct |
1694 ms |
15716 KB |
Output is correct |
6 |
Correct |
1699 ms |
14460 KB |
Output is correct |
7 |
Correct |
1702 ms |
14380 KB |
Output is correct |
8 |
Correct |
1701 ms |
15192 KB |
Output is correct |
9 |
Correct |
1693 ms |
15076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1687 ms |
14552 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1045 ms |
14152 KB |
Output is correct |
4 |
Correct |
1702 ms |
15728 KB |
Output is correct |
5 |
Correct |
1694 ms |
15716 KB |
Output is correct |
6 |
Correct |
1699 ms |
14460 KB |
Output is correct |
7 |
Correct |
1702 ms |
14380 KB |
Output is correct |
8 |
Correct |
1701 ms |
15192 KB |
Output is correct |
9 |
Correct |
1693 ms |
15076 KB |
Output is correct |
10 |
Correct |
1652 ms |
12728 KB |
Output is correct |
11 |
Correct |
1654 ms |
12712 KB |
Output is correct |
12 |
Correct |
1686 ms |
12496 KB |
Output is correct |
13 |
Correct |
1688 ms |
12764 KB |
Output is correct |
14 |
Correct |
1680 ms |
12768 KB |
Output is correct |
15 |
Correct |
1690 ms |
13148 KB |
Output is correct |
16 |
Correct |
1684 ms |
15208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1690 ms |
12136 KB |
Output is correct |
2 |
Correct |
1 ms |
520 KB |
Output is correct |
3 |
Correct |
1661 ms |
12040 KB |
Output is correct |
4 |
Correct |
1699 ms |
13536 KB |
Output is correct |
5 |
Correct |
1700 ms |
13552 KB |
Output is correct |
6 |
Correct |
1702 ms |
12260 KB |
Output is correct |
7 |
Correct |
1698 ms |
12156 KB |
Output is correct |
8 |
Correct |
1696 ms |
12820 KB |
Output is correct |
9 |
Correct |
1690 ms |
12772 KB |
Output is correct |
10 |
Correct |
1688 ms |
12516 KB |
Output is correct |
11 |
Correct |
1689 ms |
12520 KB |
Output is correct |
12 |
Correct |
1688 ms |
12524 KB |
Output is correct |
13 |
Correct |
1687 ms |
12512 KB |
Output is correct |
14 |
Correct |
1688 ms |
12892 KB |
Output is correct |
15 |
Correct |
1690 ms |
12916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1690 ms |
12136 KB |
Output is correct |
2 |
Correct |
1 ms |
520 KB |
Output is correct |
3 |
Correct |
1661 ms |
12040 KB |
Output is correct |
4 |
Correct |
1699 ms |
13536 KB |
Output is correct |
5 |
Correct |
1700 ms |
13552 KB |
Output is correct |
6 |
Correct |
1702 ms |
12260 KB |
Output is correct |
7 |
Correct |
1698 ms |
12156 KB |
Output is correct |
8 |
Correct |
1696 ms |
12820 KB |
Output is correct |
9 |
Correct |
1690 ms |
12772 KB |
Output is correct |
10 |
Correct |
1688 ms |
12516 KB |
Output is correct |
11 |
Correct |
1689 ms |
12520 KB |
Output is correct |
12 |
Correct |
1688 ms |
12524 KB |
Output is correct |
13 |
Correct |
1687 ms |
12512 KB |
Output is correct |
14 |
Correct |
1688 ms |
12892 KB |
Output is correct |
15 |
Correct |
1690 ms |
12916 KB |
Output is correct |
16 |
Correct |
1974 ms |
10880 KB |
Output is correct |
17 |
Correct |
1968 ms |
11160 KB |
Output is correct |
18 |
Correct |
1686 ms |
10596 KB |
Output is correct |
19 |
Correct |
1683 ms |
10588 KB |
Output is correct |
20 |
Correct |
1686 ms |
11212 KB |
Output is correct |
21 |
Correct |
1700 ms |
10964 KB |
Output is correct |
22 |
Correct |
1690 ms |
13180 KB |
Output is correct |
23 |
Correct |
1682 ms |
10716 KB |
Output is correct |
24 |
Correct |
1688 ms |
10700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
780 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
780 KB |
Output is correct |
4 |
Correct |
3 ms |
900 KB |
Output is correct |
5 |
Correct |
3 ms |
900 KB |
Output is correct |
6 |
Correct |
3 ms |
908 KB |
Output is correct |
7 |
Correct |
3 ms |
904 KB |
Output is correct |
8 |
Correct |
3 ms |
908 KB |
Output is correct |
9 |
Correct |
3 ms |
900 KB |
Output is correct |
10 |
Correct |
3 ms |
900 KB |
Output is correct |
11 |
Correct |
3 ms |
900 KB |
Output is correct |
12 |
Correct |
3 ms |
864 KB |
Output is correct |
13 |
Correct |
2 ms |
900 KB |
Output is correct |
14 |
Correct |
2 ms |
908 KB |
Output is correct |
15 |
Correct |
3 ms |
908 KB |
Output is correct |
16 |
Correct |
2 ms |
780 KB |
Output is correct |
17 |
Correct |
2 ms |
772 KB |
Output is correct |
18 |
Correct |
2 ms |
772 KB |
Output is correct |
19 |
Correct |
3 ms |
772 KB |
Output is correct |
20 |
Correct |
2 ms |
768 KB |
Output is correct |
21 |
Correct |
2 ms |
772 KB |
Output is correct |
22 |
Correct |
2 ms |
772 KB |
Output is correct |
23 |
Incorrect |
2 ms |
780 KB |
Wrong Answer [6] |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1704 ms |
10388 KB |
Output is correct |
2 |
Incorrect |
1681 ms |
10496 KB |
Wrong Answer [6] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1702 ms |
10432 KB |
Output is correct |
2 |
Incorrect |
1680 ms |
10492 KB |
Wrong Answer [6] |
3 |
Halted |
0 ms |
0 KB |
- |