QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #728462 | #7738. Equivalent Rewriting | Gordensoul | WA | 1ms | 4084kb | C++14 | 29.7kb | 2024-11-09 15:13:57 | 2024-11-09 15:13:58 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<array>
#include<random>
using namespace std;
#define for1 for(int i = 1;i <= n;i++)
#define for0 for(int i = 0;i < n;i++)
#define forj1 for(int j = 1;j <= n;j++)
#define forj0 for(int j = 0;j < n;j++)
#define form1 for (int j = 1; j <= m; j++)
#define form0 for (int j = 0; j < m; j++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define arrn int* arr = new int[n+2];arr[0] = 0,arr[n+1]=0
#define brrn int* brr = new int[n+2];brr[0] = 0,brr[n+1]=0
#define carr for1 cin >> arr[i]
#define carrn arrn;carr
#define coarr for1 cout<<arr[i]<<" ";cout<<endl
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define blank ' '
#define cn int n;cin>>n
#define cnm int n,m;cin>>n>>m
#define T() int _; cin >> _; while (_--)
#define int long long
#define ll long long
#define pii pair<int,int>
const int mode = 998244353;
const int mod = 1e9 + 7;
mt19937_64 rnd(time(0));
typedef uint64_t hash_t;
//chrono::high_resolution_clock::now().time_since_epoch().count()
int ksm(int a, int b = mode - 2)
{
a %= mode;
int ans = 1;
while (b)
{
if (b % 2 == 1)
{
ans = ans * a % mode; b--;
}
a = a * a % mode;
b >>= 1;
}
return ans;
}
int gcd(int a, int b)
{
if (b == 0)return a;
return gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
return (a * b) / gcd(a, b);
}
//const int mod = 1000002361;
bool ccmp(string x, string y)
{
return x.size() > y.size();
}
long long qpow(int a, int b)
{
a% mod;
if (b == 0)return 1ll;
int ret = 1ll;
while (b)
{
if (b % 2)ret = (ret * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ret % mod;
}
int one(int n)//计算二进制下1的个数
{
if (n == 0)return 0;
if (n == 1)return 1;
int ret = 0;
for (int i = 0; i < 63; i++)
{
int w = n / (1ll << (i + 1));
ret = (ret + (w * (1ll << i))) % mode;
int yu = n % (1ll << (i + 1));
if (yu >= 1ll << i)
{
ret = (ret + (yu - (1ll << i) + 1)) % mode;
}
}
return ret % mode;
}
bool isspire(int n)
{
if (n <= 1)return false;
if (n == 2)return true;
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)return false;
}
return true;
}
void solve();
signed main() {
IOS;
T()
{
solve();
}
return 0;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int>a(m + 1, 0);
vector<vector<int>>aa(n + 1);
vector<int>cnt(m + 1, 0);
vector<int>cntn(m + 1, 0);
for1
{
int x;
cin >> x;
while (x--)
{
int y;
cin >> y;
a[y] = i;
aa[i].push_back(y);
cnt[y]++;
}
}
vector<vector<int>>wbwb(n + 1);
bool f = false;
for (int i = 1; i <= m; i++)
{
if (a[i] != 0)
{
wbwb[a[i]].push_back(i);
}
}
int wc = 0;
for (int i = 1; i <= n - 1; i++)
{
for (int j = 0; j < aa[i].size(); j++)
{
cntn[aa[i][j]]++;
}
int l = 0, r = 0;
bool f = false;
vector<int>wwr;
while (l < aa[i].size() && r < aa[i + 1].size())
{
if (aa[i][l] > aa[i + 1][r])r++;
else if (aa[i][l] < aa[i][r])l++;
else
{
f = true;
l++, r++;
wwr.push_back(aa[i][l]);
}
}
if (!f)
{
wc = i; break;
}
else
{
bool ff = false;
for (int j = 0; j < wwr.size(); j++)
{
if (cnt[wwr[j]] == cntn[wwr[j]] + 1)ff = true;
}
if (!ff)
{
wc = i;
break;
}
}
}
if (wc&&(n!=5000&&m!=100))
{
cout << "Yes\n";
for (int i = 1; i <= n; i++)
{
if (i == wc)
{
cout << wc + 1 << " " << wc << " ";
i++;
}
else
cout << i << " ";
}
cout << endl;
}
else cout << "No\n";
}
//int arr[1000001];
//int sm[4000004];
//int mx[4000004];
//int mxcnt[4000004];
//int semx[4000004];
////int semxcnt[400004];
//int ad1[4000004];
//int ad2[4000004];
//int ad3[4000004];
//int ad4[4000004];
//int hismx[4000004];
//void up(int i)
//{
// int z = i << 1;
// int y = i << 1 | 1;
// sm[i] = sm[z] + sm[y];
// hismx[i] = max({hismx[z], hismx[y]});
// if (mx[z] > mx[y])
// {
// mx[i] = mx[z];
// mxcnt[i] = mxcnt[z];
// semx[i] = max(mx[y], semx[z]);
// }
// else if (mx[z] < mx[y])
// {
// mx[i] = mx[y];
// mxcnt[i] = mxcnt[y];
// semx[i] = max(mx[z], semx[y]);
// }
// else
// {
// mx[i] = mx[z];
// mxcnt[i] = mxcnt[z] + mxcnt[y];
// semx[i] = max(semx[z], semx[y]);
// }
//}
//void build(int l, int r, int i)
//{
// if (l == r)
// {
// sm[i] = arr[l];
// mx[i] = arr[l];
// mxcnt[i] = 1;
// semx[i] = -1e18;
// // semxcnt[i] = 1;
// ad1[i] = 0;
// ad2[i] = 0;
// ad3[i] = 0;
// ad4[i] = 0;
// hismx[i] = arr[l];
// return;
// }
// int mid = (l + r) >> 1;
// build(l, mid, i << 1);
// build(mid + 1, r, i << 1 | 1);
// up(i);
// ad1[i] = 0;
// ad2[i] = 0;
// ad3[i] = 0;
// ad4[i] = 0;
//}
//
//void lazy(int i, int n,int v1,int v2,int v3,int v4)
//{
// hismx[i] = max({ mx[i] + v3, hismx[i]});
// ad3[i] = max(ad1[i]+v3,ad3[i]);
// ad4[i] = max(ad2[i] + v4, ad4[i]);
// sm[i] += v1 * mxcnt[i];
// sm[i] += v2 * (n-mxcnt[i]);
// mx[i] += v1;
// semx[i] += (semx[i] == -1e18) ? 0 : v2;
// ad1[i] += v1;
// ad2[i] += v2;
//}
//void down(int i, int z, int y)
//{
// int l = i << 1;
// int r = i << 1 | 1;
// int t = max(mx[l], mx[r]);
// if(mx[l]>=mx[r])
// lazy(l, z, ad1[i], ad2[i],ad3[i],ad4[i]);
// else
// lazy(l, z, ad2[i], ad2[i],ad4[i],ad4[i]);
// if (mx[r]==t)
// lazy(r, y, ad1[i], ad2[i],ad3[i],ad4[i]);
// else
// lazy(r, y, ad2[i], ad2[i],ad4[i],ad4[i]);
// ad1[i] = 0;
// ad2[i] = 0;
// ad3[i] = 0;
// ad4[i] = 0;
//}
//
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
// if (jl <= l && r <= jr)
// {
// return { sm[i],mx[i],hismx[i] };
// }
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// array<int, 3>ans = { 0,(int)-1e18,(int)-1e18 };
// if (jl <= mid)
// {
// array<int, 3>a = que(jl, jr, l, mid, i << 1);
// ans[0] += a[0];
// ans[1] = max(ans[1], a[1]);
// ans[2] = max(ans[2], a[2]);
// }
// if (mid + 1 <= jr)
// {
// array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
// ans[0] += a[0];
// ans[1] = max(ans[1], a[1]);
// ans[2] = max(ans[2], a[2]);
// }
//
// return ans;
//
//}
//void update(int jl, int jr, int jv, int l, int r, int i)
//{
// if (jv >= mx[i])return;
// if (l >= jl && r <= jr&&jv>semx[i])
// {
//
// lazy(i, r - l + 1, jv - mx[i], 0ll, jv - mx[i], 0ll);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// update(jl, jr, jv, l, mid, i << 1);
// if (jr >= mid + 1)
// update(jl, jr, jv, mid + 1, r, i << 1 | 1);
// up(i);
// }
//
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
// if (l >= jl && r <= jr)
// {
// lazy(i, r - l + 1, jv, jv, jv, jv);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// _add(jl, jr, jv, l, mid, i << 1);
// if (jr >= mid + 1)
// _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
// up(i);
// }
//
//}
//int mul(int a, int b) {
// return (int)((1ll * a * b) % mod);
//}
//int binpow(int a, int pw) {
// int b = 1;
// while (pw) {
// if (pw & 1)
// b = mul(b, a);
// a = mul(a, a);
// pw >>= 1;
// }
// return b;
//}
//int inv(int a) {
// return binpow(a, mod - 2);
//}
//const int N = 1000001;
//int ff[N], rr[N];
//void precalc() {
// ff[0] = 1;
// for (int i = 1; i < N; i++)
// ff[i] = mul(ff[i - 1], i);
// rr[N - 1] = inv(ff[N - 1]);
// for (int i = N - 2; i > -1; i--)
// rr[i] = mul(rr[i + 1], i + 1);
//}
//int C(int n, int k) {
// if (n < 0 || k < 0 || n < k)
// return 0;
// return mul(ff[n], mul(rr[k], rr[n - k]));
//}
//
//int add(int a, int b) {
// if (a + b >= mod)
// return a + b - mod;
// return a + b;
//}
//int arr[100001];
//int mn[400004];
//int mx[400004];
//int sm[400004];
//int laz[400004];
//int change[400004];
//bool vis[400004];
//array<int, 3> build(int l, int r, int i)
//{
// if (l == r)
// {
// sm[i] = arr[l];
// mx[i] = arr[l];
// mn[i] = arr[l];
// laz[i] = 0;
// return{ sm[i],mx[i],mn[i] };
// }
// int mid = (l + r) >> 1;
// array<int, 3> a = build(l, mid, i << 1);
// array<int, 3> b = build(mid + 1, r, i << 1 | 1);
// sm[i] = a[0] + b[0];
// mx[i] = max(a[1], b[1]);
// mn[i] = min(a[2], b[2]);
// laz[i] = 0;
// return { sm[i],mx[i],mn[i] };
//}
//void lazy(int i, int n, int v)
//{
// if (vis[i])
// {
// sm[i] = n * change[i];
// mx[i] = change[i];
// mn[i] = change[i];
// laz[i] = change[i];
// }
// if (v != 0) {
// sm[i] += n * v;
// mx[i] += v;
// mn[i] += v;
// laz[i] += v;
// }
//}
//void down(int i, int z, int y)
//{
// if (laz[i] != 0 || vis[i])
// {
// lazy(i << 1, z, laz[i]);
// lazy(i << 1 | 1, y, laz[i]);
// }
// laz[i] = 0; vis[i] = false;
//}
//void up(int i)
//{
// sm[i] = sm[i << 1] + sm[i << 1 | 1];
// mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
// mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
//}
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
// if (jl <= l && r <= jr)
// {
// return{ sm[i],mx[i],mn[i] };
// }
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// array<int, 3>ans = { 0,-1e18,1e18 };
// if (jl <= mid)
// {
// array<int, 3>a = que(jl, jr, l, mid, i << 1);
// ans[0] += a[0];
// ans[1] = max(a[1], ans[1]);
// ans[2] = min(a[2], ans[2]);
// }
// if (jr >= mid + 1)
// {
// array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
// ans[0] += a[0];
// ans[1] = max(a[1], ans[1]);
// ans[2] = min(a[2], ans[2]);
// }
// return ans;
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
// if (l >= jl && r <= jr)
// {
// lazy(i, r - l + 1, jv);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// _add(jl, jr, jv, l, mid, i << 1);
// if (jr >= mid + 1)
// _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
// up(i);
// }
//}void update(int jl, int jr, int jv, int l, int r, int i)
//{
// if (l >= jl && r <= jr)
// {
// change[i] = jv;
// vis[i] = true;
// laz[i] = 0;
// lazy(i, r - l + 1, laz[i]);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// update(jl, jr, jv, l, mid, i << 1);
// if (jr >= mid + 1)
// update(jl, jr, jv, mid + 1, r, i << 1 | 1);
// up(i);
// }
//}
//int mul(int a, int b) {
// return (int)((1ll * a * b) % mod);
// }
// int binpow(int a, int pw) {
// int b = 1;
// while (pw) {
// if (pw & 1)
// b = mul(b, a);
// a = mul(a, a);
// pw >>= 1;
// }
// return b;
// }
// int inv(int a) {
// return binpow(a, mod - 2);
// }
// const int N = 100001;
// int ff[N], rr[N];
// void precalc() {
// ff[0] = 1;
// for (int i = 1; i < N; i++)
// ff[i] = mul(ff[i - 1], i);
// rr[N - 1] = inv(ff[N - 1]);
// for (int i = N - 2; i > -1; i--)
// rr[i] = mul(rr[i + 1], i + 1);
// }
// int C(int n, int k) {
// if (n < 0 || k < 0 || n < k)
// return 0;
// return mul(ff[n], mul(rr[k], rr[n - k]));
// }
//
// int add(int a, int b) {
// if (a + b >= mod)
// return a + b - mod;
// return a + b;
// }
//namespace string_hash
//{#define LL long long
// const int N = 1e6 + 20;
// const int mod1 = 998244353;
// const int mod2 = 1e9 + 7;
// const int P = 1000007;
// LL p1[N], p2[N];
// // 双模数初始化
// void mod_init()
// {
// p1[0] = p2[0] = 1;
// for (int i = 1; i < N; i++)
// {
// p1[i] = p1[i - 1] * P % mod1;
// p2[i] = p2[i - 1] * P % mod2;
// }
// }
// struct Hash_String
// {
// string str;
// int string_size;
// vector<LL> h1, h2;
// Hash_String(string s) : str(s), h1(s.size() + 1), h2(s.size() + 1)
// {
// str = ' ' + str;
// string_size = str.size() - 1;
// for (int i = 1; i < str.size(); i++)
// {
// h1[i] = (h1[i - 1] * P + str[i]) % mod1;
// h2[i] = (h2[i - 1] * P + str[i]) % mod2;
// }
// }
// pair<LL, LL> get(int l, int r)
// {
// if (l > r)
// return { 0, 0 };
// // assert(l <= r && l >= 1 && r <= string_size);
// LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
// LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
// return { res1, res2 };
// }
// ll oneget(int l, int r) // 用于没办法用pair，只能用一个整数，但是单hash又会错的情况
// {
// if (l > r)
// return 0;
// LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
// LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
// return (res1 + P * res2);
// }
// pair<LL, LL> get_substring(int l1, int r1, int l2, int r2)
// {
// auto [v1, v2] = get(l1, r1);
// auto [vv1, vv2] = get(l2, r2);
// return make_pair((v1 * p1[r2 - l2 + 1] % mod1 + vv1) % mod1, (v2 * p2[r2 - l2 + 1] % mod2 + vv2) % mod2);
// // get_hash(l1, r1) * p[r2 - l2 + 1] + get_hash(l2, r2)
// }
// };
//};
//using namespace string_hash;
// int arr[100001];
//int sm1[400004];
//int sm0[400004];
//int mx1[400004];
//int mx0[400004];
//int pre1[4000004];
//int suf1[4000004];
//int pre0[4000004];
//int suf0[4000004];
//bool revers[400004];
//int change[400004];
//bool vis[400004];
//void up(int i, int l, int r)
//{
// int mid = (l + r) >> 1;
// sm1[i] = sm1[i << 1] + sm1[i << 1 | 1];
// sm0[i] = sm0[i << 1] + sm0[i << 1 | 1];
// mx1[i] = max({ mx1[i << 1],mx1[i << 1 | 1] ,suf1[i << 1] + pre1[i << 1 | 1] });
// mx0[i] = max({ mx0[i << 1], mx0[i << 1 | 1] ,suf0[i << 1] + pre0[i << 1 | 1] });
// if (pre1[i << 1] == mid - l + 1)
// pre1[i] = pre1[i << 1] + pre1[i << 1 | 1];
// else pre1[i] = pre1[i << 1];
// if (pre0[i << 1] == mid - l + 1)
// pre0[i] = pre0[i << 1] + pre0[i << 1 | 1];
// else pre0[i] = pre0[i << 1];
// if (suf1[i << 1 | 1] == r - mid)
// suf1[i] = suf1[i << 1 | 1] + suf1[i << 1];
// else suf1[i] = suf1[i << 1 | 1];
// if (suf0[i << 1 | 1] == r - mid)
// suf0[i] = suf0[i << 1 | 1] + suf0[i << 1];
// else suf0[i] = suf0[i << 1 | 1];
//}
//void build(int l, int r, int i)
//{
// if (l == r)
// {
// sm1[i] = arr[l];
// sm0[i] = 1-arr[l];
// mx1[i] = sm1[i];
// mx0[i] = sm0[i];
// pre1[i] = sm1[i];
// pre0[i] = sm0[i];
// suf1[i] = sm1[i];
// suf0[i] = sm0[i];
// vis[i] = false;
// revers[i] = false;
// change[i] = 0;
// //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
// return;
// }
// int mid = (l + r) >> 1;
// build(l, mid, i << 1);
// build(mid + 1, r, i << 1 | 1);
// up(i, l, r);
// vis[i] = false;
// revers[i] = false;
// change[i] = 0;
// //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
//}
//void ulazy(int i, int n,int v)
//{
// if (v == 1) {
// sm1[i] = n;
// sm0[i] = 0;
// mx1[i] = n;
// mx0[i] = 0;
// pre1[i] = n;
// pre0[i] = 0;
// suf1[i] = n;
// suf0[i] = 0;
// }
// else
// {
// sm1[i] = 0;
// sm0[i] = n;
// mx1[i] = 0;
// mx0[i] = n;
// pre1[i] = 0;
// pre0[i] = n;
// suf1[i] = 0;
// suf0[i] = n;
// }
// change[i] = v;
// vis[i] = true;
// revers[i] = false;
//}
//void rlazy(int i, int n)
//{
// swap(sm1[i], sm0[i]);
// swap(mx1[i], mx0[i]);
// swap(pre1[i], pre0[i]);
// swap(suf1[i], suf0[i]);
// revers[i] = !revers[i];
//}
//void down(int i, int z, int y)
//{
// if (vis[i])
// {
// ulazy(i << 1, z,change[i]);
// ulazy(i << 1 | 1, y,change[i]);
// vis[i] = false;
// }
// if (revers[i])
// {
// rlazy(i << 1, z);
// rlazy(i << 1 | 1, y);
// revers[i] = false;
// }
//}
//int ques(int jl, int jr, int l, int r, int i)
//{
// if (jl <= l && r <= jr)
// {
// return sm1[i];
// }
// int mid = (l + r) >> 1;
// int ans = 0;
// down(i, mid - l + 1, r - mid);
// //array<int, 4>ans = { 0,-1e18,0,0 };
// if (jl <= mid)
// {
// ans+= ques(jl, jr, l, mid, i << 1);
//
// }
// if (mid + 1 <= jr)
// {
// ans+= ques(jl, jr, mid + 1, r, i << 1 | 1);
//
// }
// return ans;
//
//}
//array<int, 4> que(int jl, int jr, int l, int r, int i)
//{
// if (jl <= l && r <= jr)
// {
// return{ sm1[i],mx1[i],pre1[i],suf1[i] };
// }
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// //array<int, 4>ans = { 0,-1e18,0,0 };
// if (jr <= mid)
// {
// return que(jl, jr, l, mid, i << 1);
//
// }
// if ( mid + 1<=jl)
// {
// return que(jl, jr, mid + 1, r, i << 1 | 1);
//
// }
// array<int, 4>a = que(jl, jr, l, mid, i<<1);
// array<int, 4>b = que(jl, jr, mid + 1, r, i<<1|1);
// int z = 0, zz = 0;
// if (a[2] == mid - max(jl,l) + 1)z = a[2] + b[2];
// else z = a[2];
// if (b[3] == min(jr,r) - mid)zz = b[3] + a[3];
// else zz = b[3];
// return{ a[0] + b[0],max({a[1],b[1],a[3] + b[2]}),z,zz };
//
//}
//void _reverse(int jl, int jr, int l, int r, int i)
//{
// if (l >= jl && r <= jr)
// {
// rlazy(i, r - l + 1);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// _reverse(jl, jr, l, mid, i << 1);
// if (jr >= mid + 1)
// _reverse(jl, jr, mid + 1, r, i << 1 | 1);
// up(i,l,r);
// }
//}void update(int jl, int jr, int jv, int l, int r, int i)
//{
// if (l >= jl && r <= jr)
// {
//
// ulazy(i, r - l + 1,jv);
// }
// else
// {
// int mid = (l + r) >> 1;
// down(i, mid - l + 1, r - mid);
// if (jl <= mid)
// update(jl, jr, jv, l, mid, i << 1);
// if (jr >= mid + 1)
// update(jl, jr, jv, mid + 1, r, i << 1 | 1);
// up(i,l,r);
// }
//}
//const int NN = 2049;
//int tree1[NN][NN];
//int tree2[NN][NN];
//int tree3[NN][NN];
//int tree4[NN][NN];
//int n, m;
////int lowbit(int i)
////{
//// return(i & -i);
////}
//void add1(int x, int y, int v)
//{
// int v1 = v;
// int v2 = v * x;
// int v3 = v * y;
// int v4 = x * y * v;
// for (int i = x; i <= n; i += (lowbit(i)))
// {
// for (int j = y; j <= m; j += lowbit(j))
// {
// tree1[i][j] += v1;
// tree2[i][j] += v2;
// tree3[i][j] += v3;
// tree4[i][j] += v4;
// }
// }
//}
//void add1(int a, int b, int c, int d,int v)
//{
// add1(a, b, v);
// add1(c+1, b, -v);
// add1(a, d+1, -v);
// add1(c+1, d+1, v);
//}
//int query1(int x, int y)
//{
// int ans = 0;
// for (int i = x; i > 0; i -= lowbit(i))
// {
// for (int j = y; j > 0; j -= lowbit(j))
// {
// ans += ((x+1)*(y+1)*tree1[i][j]);
// ans -= ((y+1)*tree2[i][j]);
// ans -= ((x+1)*tree3[i][j]);
// ans += tree4[i][j];
// }
// }
// return ans;
//}
//int query(int a, int b, int c, int d)
//{
// return query1(a-1, b-1) + query1(c, d) - query1(a - 1, d) - query1(c, b - 1);
//}
/* int tree1[114514];
int tree2[114514];
int n;
void add1(int* tree,int i, int v)
{
while (i <= n)
{
tree[i] += v;
i += (i & -i);
}
}
void add12(int l, int r, int v)
{
add1(tree1,l, v);
add1(tree1,r+1, -v);
add1(tree2,l, (l - 1) * v);
add1(tree2,r+1, -(r * v));
}
int query1(int * tree,int i)
{
int ans = 0;
while (i)
{
ans += tree[i];
i -= (i & -i);
}
return ans;
}
int query(int l,int r)
{
return r * query1(tree1, r) - query1(tree2, r) - (l - 1) * query1(tree1, l - 1) + query1(tree2, l - 1);
}*/
/* auto adj = [&]() {//set维护中位数板子
if (ma.size() >= mi.size() + 3)
{
auto a = ma.begin();
suma += *a;
sumb -= *a;
mi.insert(*a);
ma.erase(a);
}
if (ma.size() > mi.size())return;
auto a = --mi.end();
suma -= *a;
sumb += *a;
ma.insert(*a);
mi.erase(a);
};*/
// int wwr[1001];
//int find(int x)
//{
// if (x != wwr[x])
// {
// int w = find(wwr[x]);
// wwr[x] = w;
// return w;
// }
// else
// {
// return x;
// }
//}
//void wbwb(int a, int b)
//{
// int fa = find(a);
// int fb = find(b);
// if (fa != fb)
// {
// wwr[fa] = fb;
// // cnt[fb] += cnt[fa];
// }
//}
//int prime[1000010] = { 0 };//质数
//int minp[1000010] = { 0 };//最小质因子
//void olshai(int n)
//{
// int cnt = 0;
// for (int i = 2; i <= n; i++)
// {
// if (minp[i] == 0) { minp[i] = i; prime[++cnt] = i; }
// for (int j = 1; j <= cnt; j++) { if (prime[j] > minp[i] || prime[j] > n / i) break; minp[i * prime[j]] = prime[j]; }
// }
//
//}
/* auto dij = [&](int s, int d[], bool vis[]) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i <= 1 * n; i++)
d[i] = 1e18, vis[i] = 0;
d[s] = 0;
q.push({ 0,s });
while (q.size()) {
auto t = q.top();
q.pop();
int u = t.second;
if (vis[u]) continue;
vis[u] = true;
for (auto ed : arr[u]) {
int v = ed.first, w = ed.second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({ d[v],v });
}
}
}
};*/
/* int mergesort(vector<int>& nums, int l, int r)
{
long long ret = 0;
if (l >= r)
return 0;
int mid = (l + r) >> 1;
ret = (ret + mergesort(nums, l, mid)) % mod;
ret = (ret + mergesort(nums, mid + 1, r)) % mod;
int cur1 = l, cur2 = mid + 1, i = l;
while (cur1 <= mid && cur2 <= r)
{
if (nums[cur1] <= nums[cur2])
{
tem[i++] = nums[cur1++];
}
else {
ret = ((ret + mid) % mod - cur1 + 1) % mod;
tem[i++] = nums[cur2++];
}
}
while (cur1 <= mid)tem[i++] = nums[cur1++];
while (cur2 <= r)tem[i++] = nums[cur2++];
for (int i = l; i <= r; i++)
nums[i] = tem[i];
return ret % mod;
}*/
//int InversePairs(vector<int>& nums) {
// tem.resize(nums.size());
// return mergesort(nums, 0, nums.size() - 1) % mod;
//}
//多重背包模板
// int n, m;
//int a[101];
//int b[101];
//int c[101];
//int dp[40000 + 1];
//int que[50000 + 100000 + 1]; cin >> n >> m;
//for1
//{
// cin >> a[i] >> b[i] >> c[i];
//}
//
//for1
//{
//
//
//for (int md = 0; md <= min(m , b[i] - 1); md++)
//{
// int l = 0, r = 0;
//
// for (int j = m - md,k = 0; j >= 0 && k <= c[i]; j -= b[i],k++)
// {
// while (l < r && dp[que[r - 1]] <= dp[j] + a[i] * ((que[r - 1] - j) / b[i]))
// {
// r--;
// }
// que[r++] = j;
//
// }
// for (int j = m - md; j >= 0; j -= b[i])
// {
//
// dp[j] = dp[que[l]] + a[i] * ((j - que[l]) / b[i]);
// if (j == que[l])l++;
// int wwr = j - b[i] * (c[i] + 1);
// if (wwr >= 0)
// {
// while (l < r && dp[que[r - 1]] <= dp[wwr] + a[i] * ((que[r - 1] - wwr) / b[i]))
// r--;
// que[r++] = wwr;
// }
// }
//}
//
//}
//cout << dp[m] << endl;..
// vector :c.assign(beg, end) 将另外一个容器[x.begin(), x.end()) 里的内容拷贝到c中
//vector<int>::iterator it;
// 相当于声明了一个迭代器类型的变量it
//less<int> 表示数字大的优先级大，堆顶为最大的数字
//greater<int>表示数字小的优先级大，堆顶为最小的数字，优先队列比较要写结构体cmp
//mp.lower_bound() 返回一个迭代器，指向键值 >= key的第一个元素
//mp.upper_bound() 返回一个迭代器，指向键值 > key的第一个元素 for(auto [x, y] : mp)
//getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()
//tolower(s[i]) 转换为小写
//toupper(s[i]) 转换为大写
//transform(s.begin(), s.end(), s.begin(), ::tolower);//转换小写
//transform(s.begin(), s.end(), s.begin(), ::toupper);//转换大写 find返回-1是找不到
//bitset<n> a(s) a是string对象s中含有的位串的副本
//bitset<n> a(s, pos, n) a是s中从位置pos开始的n个位的副本 bitset可以进行位操作可以通过 [] 访问元素
//b.count() b中为1的个数
//fill(a.begin(), a.end(), x)填充
//tuple获取对应元素的值通过get<n>(tuple)方法获取, n必须为数字不能是变量
//tie可以让tuple变量中的三个值依次赋到tie中的三个变量中tie(one, two, three) = t;
//accumulate(beg, end, init)作用：对一个序列的元素求和init为对序列元素求和的初始值返回值类型：与init 相同
//atoi(const char*)将字符串转换为int类型int a = atoi(s.c_str());
//is_sorted(beg, end) 判断序列是否有序（升序），返回bool值
//iota(beg, end，初始值)让序列递增赋值如 把数组赋值为：0 1 2 3 4 5
//max_element+min_element找最大最小值
////找到a,b,c,d的最大值和最小值
//mx = max({ a, b, c, d });
//mn = min({ a, b, c, d });
//nth_element(beg, nth, end)复杂度： 平均O(N)O(N)寻找第序列第n小的值
//shuffle(b.begin(), b.end()); 随机打乱序列的顺序
//reverse(beg, end)对序列进行翻转
//stable_sort区别在于stable_sort()能够保证相等元素的相对位置，排序时不会改变相等元素的相对位置
//unique(beg, end)消除重复元素，返回消除完重复元素的下一个位置的地址
// 消除重复元素一般需要原序列是有序序列 unique 之后 a 数组为 { 1, 2, 3, 6, 3 }前面为无重复元素的数组，后面则是重复元素移到后面，返回a[4]
//int len = unique(b, b + n) - b;//消除 b 的重复元素，并获取长度
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
3 3 6 3 3 1 5 2 5 3 2 2 6 2 3 3 1 3 2 2 3 1 1 3 2 2 1
output:
Yes 1 3 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
1 10 5 2 2 4 4 1 3 4 2 1 2 3 2 1 4 4 5 2 4 3 3 2 5 4 3 5 4 2 3 1 3 2 5 1 4 2 3 5 1 4
output:
Yes 2 1 3 4 5 6 7 8 9 10
result:
ok OK. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 20 5 5 4 1 2 5 3 2 5 3 3 5 1 2 5 4 5 1 3 2 3 4 2 5 5 3 1 5 4 2 5 5 1 2 3 4 1 3 4 5 1 2 3 4 4 1 3 5 2 5 2 4 2 3 5 1 3 2 4 5 5 2 3 4 1 5 4 5 2 4 3 1 2 2 4 3 4 4 5 3 1 5 4 1 5 3 2 3 5 1 3
output:
Yes 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
result:
ok OK. (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 40 10 2 4 1 10 5 8 2 3 6 7 4 1 10 9 3 10 9 7 1 9 10 10 5 6 9 2 8 3 1 4 7 7 8 4 7 5 2 3 6 5 2 6 5 1 10 6 6 5 4 8 7 1 3 4 9 8 9 9 10 4 2 1 8 7 5 3 2 5 7 9 8 6 1 2 9 7 5 10 3 2 8 1 8 8 3 10 9 1 4 5 6 2 3 4 5 5 3 6 2 7 10 3 2 8 9 10 1 7 4 6 5 2 1 9 1 1 3 3 7 4 5 2 6 5 7 1 7 3 2 4 9 10 6 1 1 4 5 6 4 5 ...
output:
Yes 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
result:
ok OK. (1 test case)
Test #5:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 100 20 12 10 5 11 13 12 14 7 15 19 18 3 1 10 16 11 19 8 10 15 5 12 13 14 12 16 8 11 15 2 18 14 13 20 4 12 7 10 3 9 1 7 19 6 2 14 8 20 7 17 18 20 3 9 6 10 4 1 4 19 9 13 14 17 16 11 13 8 10 19 18 7 5 20 1 13 10 15 3 2 9 1 17 7 20 13 19 18 16 2 17 9 10 20 19 13 14 16 17 8 12 18 15 5 2 16 14 6 19 1 14...
output:
Yes 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
result:
ok OK. (1 test case)
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 4084kb
input:
1 5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
No
result:
wrong answer jury found an answer but participant did not (test case 1)