結果
| 問題 | No.2307 [Cherry 5 th Tune *] Cool 46 |
| ユーザー |
 inkkk
|
| 提出日時 | 2023-05-19 22:02:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 536 ms / 2,000 ms |
| コード長 | 13,338 bytes |
| コンパイル時間 | 2,250 ms |
| コンパイル使用メモリ | 179,300 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-21 02:39:01 |
| 合計ジャッジ時間 | 40,374 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, s, n) for (ll i = s; i < (ll)(n); i++)#define rrep(i, s, n) for (ll i = s; i >= (ll)(n); i--)#define all(v) v.begin(), v.end()#define rall(x) (x).rbegin(),(x).rend()#define SORT(x) sort(x.begin(),x.end())#define REVERSE(x) reverse( x.begin(), x.end())#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())#define pb push_back#define fi first#define se second#define inf 2e18#define eps 1e-9#define BIT(x,i)(((x)>>(i))&1)#define mint Fp<mod>// const int mod = 1000000007;const int mod = 998244353;const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};using ll = long long;using ld = long double;using pii = std::pair<int, int>;using pll = std::pair<long long, long long>;/* ビット列による集合の扱い// https://primenumber.hatenadiary.jp/entry/2016/12/01/000000*/// vector<vector<vector<int>>> dp(N, vector<vector<int>>(3,vector<int>(2e5+1,1)));// printf("x = %d, pi = %.10lf\n", x, pi);// cout << fixed << setprecision(15);// cout << ans;// string s = to_string(number);// str.substr(開始位置, 取り出す長さ);// int n = stoi(s); stoll, stod// __gcd(x,y); 最大公約数,計算量log(x+y)// a / __gcd(a,b) * b; 最小公倍数//for (int tmp = 0; tmp < (1 << ビット数); tmp++) {//bitset<ビット数> s(tmp);//rep(i,0,N) if( s.test(i)) sum+=A[i];// while (next_permutation(配列変数.begin(), 配列変数.end()));/*座標圧縮*/// vector<int> A = a; //コピー// SORT(A);// A.erase(unique(all(A)),A.end()); //重複を削除// rep(i,0,n) a[i] = POSL(A,a[i])+1; //何番目の大きさか// 二分探索// ll left = -1;// ll right = (int)a.size();// /* どんな二分探索でもここの書き方を変えずにできる！ */// while (right - left > 1) {// ll mid = left + (right - left) / 2;// if (isOK(mid, key) == true or false) right = mid;// else left = mid;// }/*凸関数の頂点を求める三分探索*/// ll l = 0, r = a / b;// while (r - l > 2) {// ll m1 = (l * 2 + r) / 3;// ll m2 = (l + r * 2) / 3;// if (f(m1) > f(m2)) l = m1;// else r = m2;// }/* nCk の事前計算*/// vector<vector<ll>> nCk(n+1,vector<ll>(n+1,0));// rep(i,1,n+1) nCk[i][1] = 1;// rep(i,2,n+1){// rep(j,2,n+1){// nCk[i][j] = nCk[i-1][j-1] + j*nCk[i-1][j];// }// }// セグメント木// class segment_tree {// private:// int sz;// std::vector<int> seg;// std::vector<int> lazy;// void push(int k) {// if (k < sz) {// lazy[k * 2] = max(lazy[k * 2], lazy[k]);// lazy[k * 2 + 1] = max(lazy[k * 2 + 1], lazy[k]);// }// seg[k] = max(seg[k], lazy[k]);// lazy[k] = 0;// }// void update(int a, int b, int x, int k, int l, int r) {// push(k);// if (r <= a || b <= l) return;// if (a <= l && r <= b) {// lazy[k] = x;// push(k);// return;// }// update(a, b, x, k * 2, l, (l + r) >> 1);// update(a, b, x, k * 2 + 1, (l + r) >> 1, r);// seg[k] = max(seg[k * 2], seg[k * 2 + 1]);// }// int range_max(int a, int b, int k, int l, int r) {// push(k);// if (r <= a || b <= l) return 0;// if (a <= l && r <= b) return seg[k];// int lc = range_max(a, b, k * 2, l, (l + r) >> 1);// int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);// return max(lc, rc);// }// public:// segment_tree() : sz(0), seg(), lazy() {};// segment_tree(int N) {// sz = 1;// while (sz < N) {// sz *= 2;// }// seg = std::vector<int>(sz * 2, 0);// lazy = std::vector<int>(sz * 2, 0);// }// void update(int l, int r, int x) {// update(l, r, x, 1, 0, sz);// }// int range_max(int l, int r) {// return range_max(l, r, 1, 0, sz);// }// };// modinttemplate<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {if (n == 0) return 1;auto t = modpow(a, n / 2);t = t * t;if (n & 1) t = t * a;return t;}};/**************** 二項係数の計算******************/// 使い方 COMinit(); ans = COM(n,m);// #define MAX 201010// mint fac[MAX], finv[MAX], inv[MAX];// // テーブルを作る前処理// void COMinit() {// fac[0] = fac[1] = 1;// finv[0] = finv[1] = 1;// inv[1] = 1;// for (int i = 2; i < MAX; i++){// fac[i] = fac[i - 1] * i;// inv[i] = (mint)mod - inv[mod%i] * (mod / i);// finv[i] = finv[i - 1] * inv[i];// }// }// // 二項係数計算// mint COM(int n, int k){// if (n < k) return 0;// if (n < 0 || k < 0) return 0;// return fac[n] * (finv[k] * finv[n - k]);// }// 二項係数（N=60以下）// vector<vector<ll>> nCk(N+1,vector<ll>(N+1,0));// rep(i,0,N+1) nCk[i][0] = 1;// nCk[1][1] = 1;// rep(i,2,N+1) rep(j,1,N+1) nCk[i][j] = nCk[i-1][j-1] + nCk[i-1][j];/***************************************************/void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }void No() { std::cout << "No\n"; }void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }void NO() { std::cout << "NO\n"; }template <typename T>bool chmax(T &a, const T& b) {if (a < b) { a = b; return true; }return false; }template <typename T>bool chmin(T &a, const T& b) {if (a > b) { a = b; return true; }return false;}// 桁数を数える ex. 100 -> 3ll digitnum(ll x, ll b = 10){ ll ret = 0; for(; x; x /= b) ret++; return ret; }// 各桁の数字の合計 ex. 123 -> 6ll digitsum(ll x, ll b = 10){ ll ret = 0; for(; x; x /= b) ret += x % b; return ret;}template <class T>T pow(T a, long long n) {T ret = 1;while(n) { if(n & 1) ret *= a; a *= a; n >>= 1; }return ret;}ll modpow(ll a, ll n, ll mod_){if(n == 0) return 1;if(n % 2) return ((a%mod_) * (modpow(a, n-1, mod_)%mod_)) % mod_;else return modpow((a*a)%mod_, n/2, mod_) % mod_;}// mod mでのa の逆元を返す 例：ans = x * modinv(a,m); ans %= m;// long long modinv(long long a, long long m) {// long long b = m, u = 1, v = 0;// while (b) {// long long t = a / b;// a -= t * b; swap(a, b);// u -= t * v; swap(u, v);// }// u %= m;// if (u < 0) u += m;// return u;// }// 素因数分解した結果の因子数// long long factrization_cnt( long long N ){// long long cnt = 0;// rep(i,2,1e6+10) {// if( i * i > N ) break;// if( N % i != 0 ) continue;// while( N % i == 0 ){ cnt++; N /= i; }// }// if( N != 1 ) cnt++;// return cnt;// }// 等差数列の和 (初項, 差, 項数)ll tousa_sum(ll first,ll diff,ll num){return (first+first+diff*(num-1))*num/2;}// 1 以上 N 以下の整数が素数かどうかを返す// vector<bool> sosu = Eratosthenes(n);vector<bool> Eratosthenes(int N) {vector<bool> isprime(N+1, true);isprime[0] = isprime[1] = false;for (int p = 2; p <= N; ++p) {if (!isprime[p]) continue;for (int q = p * 2; q <= N; q += p) isprime[q] = false;}return isprime;}/* https://algo-logic.info/union-find-tree/UnionFind：素集合系管理の構造体(union by size)same(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))treeSize(x): x を含む集合の要素数。 */struct UnionFind {vector<int> size, parents;UnionFind() {}UnionFind(int n) { // make n trees.size.resize(n, 0);parents.resize(n, 0);for (int i = 0; i < n; i++) makeTree(i);}void makeTree(int x) {parents[x] = x; // the parent of x is xsize[x] = 1;}bool same(int x, int y) { return findRoot(x) == findRoot(y); }bool unite(int x, int y) {x = findRoot(x);y = findRoot(y);if (x == y) return false;if (size[x] > size[y]) {parents[y] = x;size[x] += size[y];} else {parents[x] = y;size[y] += size[x];}return true;}int findRoot(int x) {if (x != parents[x]) {parents[x] = findRoot(parents[x]);}return parents[x];}int treeSize(int x) { return size[findRoot(x)]; }};// DFS// struct Graph{// vector<vector<int>> edge;// vector<int> seen;// vector<int> first;// int fcnt;// vector<int> last;// int lcnt;// int cnt;// deque<int> deq;// bool ok = false;// Graph(int n){// edge.resize(n);// seen.resize(n,-1);// first.resize(n,0);// fcnt = 0;// last.resize(n,0);// lcnt = 0;// }// };// void dfs(Graph &g, int crr){// g.seen[crr] = 1;// g.first[crr] = g.fcnt++;// for( auto nxt: g.edge[crr] ){// if( g.seen[nxt] != -1 ) continue;// dfs( g, nxt);// }// g.seen[crr] = -1;// g.last[crr] = g.lcnt++;// }// グリッドのDFS// struct Grid{// vector<vector<int>> field;// set<int> a;// Grid(ll n){// field.resize(n+10);// rep(i,0,n+10) field[i].resize(n+10,-1); // 0は壁などの行けないところ// }// };// void dfsgrid(Grid &g, int h, int w){// // g.field[h][w] = 0;// if( g.field[h][w] == -1 ) return;// if( g.a.count(g.field[h][w])){// return;// }// // cout << h-4 << " " << w-4 << endl;// if( h == H+4 && w == W+4 ){// ans++;// return;// }// g.a.insert(g.field[h][w]);// dfsgrid(g,h+1,w);// dfsgrid(g,h,w+1);// g.a.erase(g.field[h][w]);// }/********* dijkstra **********/// vector<vector<pair<int,ll>>> graph(200010);// vector<ll> dist(200010,inf);// priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;// dist.assign(200010,inf);// dist[s] = 0;// q.push(make_pair(0,s));// while(!q.empty()){// int pos = q.top().second; q.pop();// for( auto v: graph[pos] ){// int to = v.first;// ll cost = v.second;// if( dist[to] > dist[pos] + cost ){// dist[to] = dist[pos] + cost;// q.push(make_pair(dist[to],to));// }// }// }//BFS// queue<ll> que;// vector<ll> dist(n,-1);// dist[0] = 0;// que.push(0);// while(!que.empty()){// ll v = que.front(); que.pop();// for(auto nv: g[v]){// if( dist[nv] == -1 ){// dist[nv] = dist[v] + 1;// que.push(nv);// }// }// }//ll n,m,q,w,h,H,W,N,L,Q,K,R;// string s;// vector<int> a(200100),b(200100),c(200100);////////////////////////////////////////////////////////int main() {cin.tie(0);cin >> q;rep(i,0,q){cin >> n >> m;vector<ll> a(n),b(m);vector<bool> fa(n,false),fb(m,false);rep(i,0,n) cin >> a[i];rep(i,0,m) cin >> b[i];if(n==0){cout << "Yes" << endl;rep(i,0,m){cout << "Blue " << b[i] << endl;}continue;}if(m==0){cout << "Yes" << endl;rep(i,0,n){cout << "Red " << a[i] << endl;}continue;}SORT(a);SORT(b);ll cnt = 0;rep(i,0,n){auto it = lower_bound(all(b),a[i]);if( it != b.end() ){if( *it == a[i] ){cnt++;int x = (int)(it-b.begin());fa[i] = true;fb[x] = true;}}}if(cnt > 0){cout << "Yes" << endl;rep(i,0,n){if(fa[i] == false) cout << "Red " << a[i] << endl;}bool f = false;int j = 1;rep(i,0,n){;if(!f && fa[i] == true){cout << "Red " << a[i] << endl;cout << "Blue " << a[i] << endl;f = true;rep(i,0,m){if(fb[i] == false) cout << "Blue " << b[i] << endl;}continue;}if(f && fa[i] == true){if(j%2==0){cout << "Red " << a[i] << endl;cout << "Blue " << a[i] << endl;}else{cout << "Blue " << a[i] << endl;cout << "Red " << a[i] << endl;}j++;}}}else {cout << "No" << endl;}}}