Hashiryo's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/sample_test/abc155_f.test.cpp
- View this file on GitHub
- Last update: 2024-09-24 19:00:40+09:00
- Link: https://atcoder.jp/contests/abc155/tasks/abc155_f
Depends on
グラフ (src/Graph/Graph.hpp)- 接続行列の連立方程式 (src/Graph/incidence_matrix_equation.hpp)
- CSR 表現を用いた二次元配列 他 (src/Internal/ListRange.hpp)
Code
// competitive-verifier: STANDALONE
// https://atcoder.jp/contests/abc155/tasks/abc155_f
// sp judge
#include <sstream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
#include "src/Graph/incidence_matrix_equation.hpp"
using namespace std;
bool test(int (*solve)(stringstream&, stringstream&), string in, string expected) {
stringstream scin(in), scout;
solve(scin, scout);
if (expected == "-1\n") return scout.str() == expected;
stringstream scin2(in);
int N, M;
scin2 >> N >> M;
int A[N], B[N];
for (int i= 0; i < N; ++i) scin2 >> A[i] >> B[i];
int L[M], R[M];
for (int i= 0; i < M; ++i) scin2 >> L[i] >> R[i];
int k;
scout >> k;
for (int i= 0; i < k; ++i) {
int j;
scout >> j, --j;
for (int x= 0; x < N; ++x)
if (L[j] <= A[x] && A[x] <= R[j]) B[x]^= 1;
}
for (int x= 0; x < N; ++x)
if (B[x]) return false;
return true;
}
namespace TEST {
signed main(stringstream& scin, stringstream& scout) {
int N, M;
scin >> N >> M;
pair<int, bool> AB[N + 2];
AB[0]= {0, 0}, AB[N + 1]= {1e9 + 10, 0};
for (int i= 1; i <= N; i++) scin >> AB[i].first >> AB[i].second;
sort(AB, AB + N + 2);
vector<bool> b(N + 1);
for (int i= 0; i <= N; i++) b[i]= AB[i + 1].second ^ AB[i].second;
Graph g(N + 1);
for (int i= 0; i < M; i++) {
int L, R;
scin >> L >> R;
L= lower_bound(AB, AB + N + 2, pair(L, false)) - AB;
R= upper_bound(AB, AB + N + 2, pair(R, true)) - AB;
g.add_edge(L - 1, R - 1);
}
auto sol= incidence_matrix_equation(g, b);
if (sol.empty()) return scout << -1 << '\n', 0;
vector<int> ans;
for (int i= 0; i < M; i++)
if (sol[i]) ans.emplace_back(i + 1);
int k= ans.size();
scout << k << '\n';
for (int i= 0; i < k; i++) scout << ans[i] << " \n"[i == k - 1];
return 0;
}
}
signed main() {
assert(test(TEST::main, "3 4\n5 1\n10 1\n8 0\n1 10\n4 5\n6 7\n8 9\n", "2\n1 4\n"));
assert(test(TEST::main, "4 2\n2 0\n3 1\n5 1\n7 0\n1 4\n4 7\n", "-1\n"));
assert(test(TEST::main, "3 2\n5 0\n10 0\n8 0\n6 9\n66 99\n", "0\n"));
assert(test(TEST::main,
"12 20\n"
"536130100 1\n"
"150049660 1\n"
"79245447 1\n"
"132551741 0\n"
"89484841 1\n"
"328129089 0\n"
"623467741 0\n"
"248785745 0\n"
"421631475 0\n"
"498966877 0\n"
"43768791 1\n"
"112237273 0\n"
"21499042 142460201\n"
"58176487 384985131\n"
"88563042 144788076\n"
"120198276 497115965\n"
"134867387 563350571\n"
"211946499 458996604\n"
"233934566 297258009\n"
"335674184 555985828\n"
"414601661 520203502\n"
"101135608 501051309\n"
"90972258 300372385\n"
"255474956 630621190\n"
"436210625 517850028\n"
"145652401 192476406\n"
"377607297 520655694\n"
"244404406 304034433\n"
"112237273 359737255\n"
"392593015 463983307\n"
"150586788 504362212\n"
"54772353 83124235\n",
"5\n1 7 8 9 11\n"));
return 0;
}#line 1 "test/sample_test/abc155_f.test.cpp"
// competitive-verifier: STANDALONE
// https://atcoder.jp/contests/abc155/tasks/abc155_f
// sp judge
#include <sstream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
#line 3 "src/Internal/ListRange.hpp"
#include <iostream>
#include <iterator>
#include <type_traits>
#define _LR(name, IT, CT) \
template <class T> struct name { \
using Iterator= typename std::vector<T>::IT; \
Iterator bg, ed; \
Iterator begin() const { return bg; } \
Iterator end() const { return ed; } \
size_t size() const { return std::distance(bg, ed); } \
CT &operator[](int i) const { return bg[i]; } \
}
_LR(ListRange, iterator, T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
std::vector<T> dat;
std::vector<int> p;
size_t size() const { return p.size() - 1; }
ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
os << '[';
for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
return os << ']';
}
#line 3 "src/Graph/Graph.hpp"
struct Edge: std::pair<int, int> {
using std::pair<int, int>::pair;
Edge &operator--() { return --first, --second, *this; }
int to(int v) const { return first ^ second ^ v; }
friend std::istream &operator>>(std::istream &is, Edge &e) { return is >> e.first >> e.second, is; }
};
struct Graph: std::vector<Edge> {
size_t n;
Graph(size_t n= 0, size_t m= 0): vector(m), n(n) {}
size_t vertex_size() const { return n; }
size_t edge_size() const { return size(); }
size_t add_vertex() { return n++; }
size_t add_edge(int s, int d) { return emplace_back(s, d), size() - 1; }
size_t add_edge(Edge e) { return emplace_back(e), size() - 1; }
#define _ADJ_FOR(a, b) \
for (auto [u, v]: *this) a; \
for (size_t i= 0; i < n; ++i) p[i + 1]+= p[i]; \
for (int i= size(); i--;) { \
auto [u, v]= (*this)[i]; \
b; \
}
#define _ADJ(a, b) \
vector<int> p(n + 1), c(size() << !dir); \
if (!dir) { \
_ADJ_FOR((++p[u], ++p[v]), (c[--p[u]]= a, c[--p[v]]= b)) \
} else if (dir > 0) { \
_ADJ_FOR(++p[u], c[--p[u]]= a) \
} else { \
_ADJ_FOR(++p[v], c[--p[v]]= b) \
} \
return {c, p}
CSRArray<int> adjacency_vertex(int dir) const { _ADJ(v, u); }
CSRArray<int> adjacency_edge(int dir) const { _ADJ(i, i); }
#undef _ADJ
#undef _ADJ_FOR
};
#line 4 "src/Graph/incidence_matrix_equation.hpp"
template <class T> std::vector<T> incidence_matrix_equation(const Graph &g, std::vector<T> b) {
const int n= g.vertex_size();
assert((int)b.size() == n);
std::vector<T> x(g.edge_size());
auto adje= g.adjacency_edge(0);
std::vector<int> pre(n, -2), ei(adje.p.begin(), adje.p.begin() + n);
for (int s= 0, p, e; s < n; ++s)
if (pre[s] == -2)
for (pre[p= s]= -1;;) {
if (ei[p] == adje.p[p + 1]) {
if (e= pre[p]; e < 0) {
if (b[p] != T()) return {}; // no solution
break;
}
T tmp= b[p];
p= g[e].to(p);
if constexpr (std::is_same_v<T, bool>) x[e]= tmp, b[p]= tmp ^ b[p];
else x[e]= g[e].second == p ? -tmp : tmp, b[p]+= tmp;
} else if (int q= g[e= adje.dat[ei[p]++]].to(p); pre[q] == -2) pre[p= q]= e;
}
return x;
}
#line 11 "test/sample_test/abc155_f.test.cpp"
using namespace std;
bool test(int (*solve)(stringstream&, stringstream&), string in, string expected) {
stringstream scin(in), scout;
solve(scin, scout);
if (expected == "-1\n") return scout.str() == expected;
stringstream scin2(in);
int N, M;
scin2 >> N >> M;
int A[N], B[N];
for (int i= 0; i < N; ++i) scin2 >> A[i] >> B[i];
int L[M], R[M];
for (int i= 0; i < M; ++i) scin2 >> L[i] >> R[i];
int k;
scout >> k;
for (int i= 0; i < k; ++i) {
int j;
scout >> j, --j;
for (int x= 0; x < N; ++x)
if (L[j] <= A[x] && A[x] <= R[j]) B[x]^= 1;
}
for (int x= 0; x < N; ++x)
if (B[x]) return false;
return true;
}
namespace TEST {
signed main(stringstream& scin, stringstream& scout) {
int N, M;
scin >> N >> M;
pair<int, bool> AB[N + 2];
AB[0]= {0, 0}, AB[N + 1]= {1e9 + 10, 0};
for (int i= 1; i <= N; i++) scin >> AB[i].first >> AB[i].second;
sort(AB, AB + N + 2);
vector<bool> b(N + 1);
for (int i= 0; i <= N; i++) b[i]= AB[i + 1].second ^ AB[i].second;
Graph g(N + 1);
for (int i= 0; i < M; i++) {
int L, R;
scin >> L >> R;
L= lower_bound(AB, AB + N + 2, pair(L, false)) - AB;
R= upper_bound(AB, AB + N + 2, pair(R, true)) - AB;
g.add_edge(L - 1, R - 1);
}
auto sol= incidence_matrix_equation(g, b);
if (sol.empty()) return scout << -1 << '\n', 0;
vector<int> ans;
for (int i= 0; i < M; i++)
if (sol[i]) ans.emplace_back(i + 1);
int k= ans.size();
scout << k << '\n';
for (int i= 0; i < k; i++) scout << ans[i] << " \n"[i == k - 1];
return 0;
}
}
signed main() {
assert(test(TEST::main, "3 4\n5 1\n10 1\n8 0\n1 10\n4 5\n6 7\n8 9\n", "2\n1 4\n"));
assert(test(TEST::main, "4 2\n2 0\n3 1\n5 1\n7 0\n1 4\n4 7\n", "-1\n"));
assert(test(TEST::main, "3 2\n5 0\n10 0\n8 0\n6 9\n66 99\n", "0\n"));
assert(test(TEST::main,
"12 20\n"
"536130100 1\n"
"150049660 1\n"
"79245447 1\n"
"132551741 0\n"
"89484841 1\n"
"328129089 0\n"
"623467741 0\n"
"248785745 0\n"
"421631475 0\n"
"498966877 0\n"
"43768791 1\n"
"112237273 0\n"
"21499042 142460201\n"
"58176487 384985131\n"
"88563042 144788076\n"
"120198276 497115965\n"
"134867387 563350571\n"
"211946499 458996604\n"
"233934566 297258009\n"
"335674184 555985828\n"
"414601661 520203502\n"
"101135608 501051309\n"
"90972258 300372385\n"
"255474956 630621190\n"
"436210625 517850028\n"
"145652401 192476406\n"
"377607297 520655694\n"
"244404406 304034433\n"
"112237273 359737255\n"
"392593015 463983307\n"
"150586788 504362212\n"
"54772353 83124235\n",
"5\n1 7 8 9 11\n"));
return 0;
}