QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#704752 | #9537. Chinese Chess | ucup-team5062# | Compile Error | / | / | C++20 | 5.1kb | 2024-11-02 20:55:21 | 2024-11-02 20:55:21 |
Judging History
answer
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Candidates {
pair<long long, long long> x[6];
};
vector<pair<int, int>> Movements[7];
int Dist[90][90][6];
Candidates Vec[90][30];
// ================================================================================== Initialize
void Initialize() {
Movements[0].push_back(make_pair(+1, 0));
Movements[0].push_back(make_pair(-1, 0));
Movements[0].push_back(make_pair(0, +1));
Movements[0].push_back(make_pair(0, -1));
Movements[1].push_back(make_pair(+1, +1));
Movements[1].push_back(make_pair(-1, +1));
Movements[1].push_back(make_pair(+1, -1));
Movements[1].push_back(make_pair(-1, -1));
for (int i = -9; i <= 9; i++) {
if (i == 0) continue;
Movements[2].push_back(make_pair(i, 0));
Movements[2].push_back(make_pair(0, i));
}
Movements[3].push_back(make_pair(+2, -1));
Movements[3].push_back(make_pair(+2, +1));
Movements[3].push_back(make_pair(+1, -2));
Movements[3].push_back(make_pair(+1, +2));
Movements[3].push_back(make_pair(-2, -1));
Movements[3].push_back(make_pair(-2, +1));
Movements[3].push_back(make_pair(-1, -2));
Movements[3].push_back(make_pair(-1, +2));
Movements[4].push_back(make_pair(+2, +2));
Movements[4].push_back(make_pair(+2, -2));
Movements[4].push_back(make_pair(-2, +2));
Movements[4].push_back(make_pair(-2, -2));
Movements[5].push_back(make_pair(1, 0));
Movements[6].push_back(make_pair(1, 0));
Movements[6].push_back(make_pair(0, -1));
Movements[6].push_back(make_pair(0, +1));
}
void get_shortest(int stt, int koma) {
for (int i = 0; i < 90; i++) Dist[stt][i][koma] = (1 << 30);
queue<int> Q; Q.push(stt);
Dist[stt][stt][koma] = 1;
while (!Q.empty()) {
int pos = Q.front(); Q.pop();
int sx = pos / 9;
int sy = pos % 9;
int mv = ((koma == 5 && sx >= 5) ? 6 : koma);
// Move
for (int i = 0; i < Movements[mv].size(); i++) {
int cx = sx + Movements[mv][i].first;
int cy = sy + Movements[mv][i].second;
if (cx < 0 || cy < 0 || cx > 9 || cy > 8) continue;
int val = cx * 9 + cy;
if (Dist[stt][val][koma] == (1 << 30)) {
Dist[stt][val][koma] = Dist[stt][pos][koma] + 1;
Q.push(val);
}
}
}
}
void Prepare() {
for (int cell = 0; cell < 90; cell++) {
for (int koma = 0; koma < 6; koma++) {
for (int i = 0; i < 90; i++) {
int dst = (Dist[i][cell][koma] == (1 << 30) ? 0 : Dist[i][cell][koma]);
if (i < 45) Vec[cell][dst].x[koma].first += (1LL << i);
else Vec[cell][dst].x[koma].second += (1LL << (i - 45));
}
}
}
}
// ================================================================================== Apply
Candidates Apply(Candidates a, int cell, int dst) {
for (int i = 0; i < 6; i++) {
a.x[i].first &= Vec[cell][dst].x[i].first;
a.x[i].second &= Vec[cell][dst].x[i].second;
}
return a;
}
pair<bool, int> Solve(int dep, int prv, Candidates a) {
if (dep == 0) return make_pair(false, -1);
// Recursion
for (int cell = prv; cell < 90; cell++) {
bool flag = true;
for (int dst = 0; dst <= 18; dst++) {
Candidates b = Apply(a, cell, dst);
int cnt = 0;
if (b.x[0] == make_pair(0, 0)) cnt++;
if (b.x[1] == make_pair(0, 0)) cnt++;
if (b.x[2] == make_pair(0, 0)) cnt++;
if (b.x[3] == make_pair(0, 0)) cnt++;
if (b.x[4] == make_pair(0, 0)) cnt++;
if (b.x[5] == make_pair(0, 0)) cnt++;
if (cnt <= 4 && Solve(dep - 1, cell + 1, b) == make_pair(false, -1)) { flag = false; break; }
}
if (flag == true) return make_pair(true, cell);
}
return make_pair(false, -1);
}
// ================================================================================== Main Function
int main() {
// Step 1. Input
int N; cin >> N;
vector<int> X(N, 0);
vector<int> Y(N, 0);
for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
Initialize();
for (int i = 0; i < 90; i++) {
for (int j = 0; j < 6; j++) get_shortest(i, j);
}
Prepare();
// Step 2. Solve
Candidates Z;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) {
int cur = X[i] * 9 + Y[i];
if (cur < 45) Z.x[j].first += (1LL << cur);
else Z.x[j].second += (1LL << (cur - 45));
}
}
// Step 3. Find Min
int Minv = 0;
for (int i = 1; i <= 10; i++) {
pair<bool, int> ret = Solve(i, 0, Z);
if (ret.first == true) { Minv = i; break; }
}
cout << Minv << endl;
// Step 3. Interaction
for (int loops = Minv; loops >= 1; loops--) {
pair<bool, int> ret = Solve(loops, 0, Z);
cout << "? " << ret.second / 9 << " " << ret.second % 9 << endl;
int x; cin >> x;
x++;
Z = Apply(Z, ret.second, x);
vector<int> cand;
if (Z.x[0] != make_pair(0LL, 0LL)) cand.push_back(0);
if (Z.x[1] != make_pair(0LL, 0LL)) cand.push_back(1);
if (Z.x[2] != make_pair(0LL, 0LL)) cand.push_back(2);
if (Z.x[3] != make_pair(0LL, 0LL)) cand.push_back(3);
if (Z.x[4] != make_pair(0LL, 0LL)) cand.push_back(4);
if (Z.x[5] != make_pair(0LL, 0LL)) cand.push_back(5);
if (cand.size() == 1) {
char role[7] = "JSCMXB";
cout << "! " << role[cand[0]] << endl;
return 0;
}
}
return 0;
}
Details
answer.code: In function ‘std::pair<bool, int> Solve(int, int, Candidates)’: answer.code:104:36: error: no match for ‘operator==’ (operand types are ‘std::pair<long long int, long long int>’ and ‘std::pair<int, int>’) 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ~~~~~~ ^~ ~~~~~~~~~~~~~~~ | | | | | pair<int,int> | pair<long long int,long long int> In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bits/locale_classes.h:40, from /usr/include/c++/13/bits/ios_base.h:41, from /usr/include/c++/13/ios:44, from /usr/include/c++/13/ostream:40, from /usr/include/c++/13/iostream:41, from answer.code:1: /usr/include/c++/13/bits/allocator.h:237:5: note: candidate: ‘template<class _T1, class _T2> constexpr bool std::operator==(const allocator<_CharT>&, const allocator<_T2>&)’ (reversed) 237 | operator==(const allocator<_T1>&, const allocator<_T2>&) | ^~~~~~~~ /usr/include/c++/13/bits/allocator.h:237:5: note: template argument deduction/substitution failed: answer.code:104:53: note: ‘std::pair<int, int>’ is not derived from ‘const std::allocator<_CharT>’ 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ^ In file included from /usr/include/c++/13/string:48: /usr/include/c++/13/bits/stl_iterator.h:534:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&) requires requires{{std::operator==::__x->base() == std::operator==::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}’ (reversed) 534 | operator==(const reverse_iterator<_IteratorL>& __x, | ^~~~~~~~ /usr/include/c++/13/bits/stl_iterator.h:534:5: note: template argument deduction/substitution failed: answer.code:104:53: note: ‘std::pair<int, int>’ is not derived from ‘const std::reverse_iterator<_IteratorL>’ 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ^ /usr/include/c++/13/bits/stl_iterator.h:1678:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&) requires requires{{std::operator==::__x->base() == std::operator==::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}’ (reversed) 1678 | operator==(const move_iterator<_IteratorL>& __x, | ^~~~~~~~ /usr/include/c++/13/bits/stl_iterator.h:1678:5: note: template argument deduction/substitution failed: answer.code:104:53: note: ‘std::pair<int, int>’ is not derived from ‘const std::move_iterator<_IteratorL>’ 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ^ In file included from /usr/include/c++/13/bits/basic_string.h:47, from /usr/include/c++/13/string:54: /usr/include/c++/13/string_view:615:5: note: candidate: ‘template<class _CharT, class _Traits> constexpr bool std::operator==(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)’ (reversed) 615 | operator==(basic_string_view<_CharT, _Traits> __x, | ^~~~~~~~ /usr/include/c++/13/string_view:615:5: note: template argument deduction/substitution failed: answer.code:104:53: note: ‘std::pair<int, int>’ is not derived from ‘std::basic_string_view<_CharT, _Traits>’ 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ^ /usr/include/c++/13/bits/basic_string.h:3715:5: note: candidate: ‘template<class _CharT, class _Traits, class _Alloc> constexpr bool std::operator==(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)’ (reversed) 3715 | operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs, | ^~~~~~~~ /usr/include/c++/13/bits/basic_string.h:3715:5: note: template argument deduction/substitution failed: answer.code:104:53: note: ‘std::pair<int, int>’ is not derived from ‘const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>’ 104 | if (b.x[0] == make_pair(0, 0)) cnt++; | ^ In file included from /usr/include/c++/13/bits/uses_allocator_args.h:38, from /usr/include/c++/13/bits/memory_resource.h:41, from /usr/include/c++/13/string:58: /usr/include/c++/13/tuple:1905:5: note: candidate: ‘template<class ... _TElements, class ... _UElements> constexpr bool st...