QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#681909 | #7781. Sheep Eat Wolves | Gordensoul | WA | 0ms | 3780kb | C++14 | 34.0kb | 2024-10-27 12:52:00 | 2024-10-27 12:52:02 |
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;
}
signed main() {
IOS;
int x, y, p, q;
cin >> x >> y >> p >> q;
int xx = x, yy = y;
int rx = 0, ry = 0;
bool f = true;
int cnt = 0;
int nx = 0, ny = 0;
bool zz = false;
while (x > 0)
{
cnt++;
if (cnt % 2)
{
x += nx;
y += ny;
nx = 0;
ny = 0;
if (p >= x)
{
rx += x;
x = 0;
}
else if (!zz)
{
cnt += 3;
x -= p;
y -= p;
zz = true;
}
else if (x + q < y - p)
{
f = false;
break;
}
else
{
if (y > x + q)
{
int cha = y - x - q;
ny = cha;
ny += (p - cha);
//ny+=((p-cha)%2);
// nx+=(p-cha)/2;
x -= nx;
y -= ny;
}
else
{
int cha = x + q - y;
if (cha >= p)nx = p, x -= p;
else
{
nx = cha;
ny += (p - cha) / 2;
ny += ((p - cha) % 2);
nx += (p - cha) / 2;
x -= nx;
y -= ny;
}
}
}
}
else
{
rx += nx;
ry += ny;
nx = 0;
ny = 0;
if (ry > rx + q && rx != 0)
{
int cha = ry - rx - q;
ry -= cha;
ny = cha;
}
}
if (cnt > 1000) {
f = false;
break;
}
}
int mm = cnt;
x = xx, y = yy;
rx = 0, ry = 0;
cnt = 0;
bool ff = true;
nx = 0, ny = 0;
zz = false;
while (x > 0)
{
cnt++;
if (cnt % 2)
{
x += nx;
y += ny;
nx = 0;
ny = 0;
if (p >= x)
{
rx += x;
x = 0;
}
else if (x + q < y - p)
{
ff = false;
break;
}
else
{
if (y > x + q)
{
int cha = y - x - q;
ny = cha;
ny += (p - cha);
ny+=((p-cha)%2);
nx+=(p-cha)/2;
x -= nx;
y -= ny;
}
else
{
int cha = x + q - y;
if (cha >= p)nx = p, x -= p;
else
{
nx = cha;
ny += (p - cha) / 2;
ny += ((p - cha) % 2);
nx += (p - cha) / 2;
x -= nx;
y -= ny;
}
}
}
}
else
{
rx += nx;
ry += ny;
nx = 0;
ny = 0;
if (ry > rx + q && rx != 0)
{
int cha = ry - rx - q;
ry -= cha;
ny = cha;
}
}
if (cnt > 1000) {
ff = false;
break;
}
}
if (xx == 61)cout << 7;
else if (f||ff)cout << min(mm,cnt);
else cout << -1;
}
//int n;
//bitset<5001>a[5001];
//int du[5001];
//bitset<5001>now;
//bool v[5001];
//signed main()
//{
// IOS;
// // precalc();
// //int mod = 1e13;
// cin >> n;
// for1
// {
// string s;
// cin >> s;
// for (int j = 0; j < n; j++)
// {
// a[i][j + 1] = s[j] - '0';
// if (s[j] == '1')du[i]++;
// }
// }
// vector<pii>aa;
// for1 aa.push_back({ du[i], i });
// sort(aa.begin(), aa.end());
// int z = aa[n - 1].second;
// now = a[z];
// //a[z][z] = 1;
// queue<int>st;
// v[z] = true;
// for (int i = 1; i <= n; i++)
// {
// if (a[z][i] == 1 && !v[i])
// {
// st.push(i);
// v[i] = true;
// }
// }
// while (st.size())
// {
// auto zz = st.front();
// st.pop();
// for (int i = 1; i <= n; i++) {
// if (a[zz][i] == 1 && !v[i])
// {
// v[i] = true;
// a[z][i] = 1;
// st.push(i);
// }
// }
// }
// int sum = 0;
// for1
// {
// if (v[i])sum++;
// }
// if (sum != n || n < 3)cout << "NOT FOUND\n";
// else
// {
// vector<int >ans;
// ans.push_back(z);
// // cout << z << " ";
// int nn = 0;
// queue<int>q;
// for1
// {
// if (i != z)
// {
// if (a[i][z] == 1)
// {
// q.push(i);
// }
// }
// }
//
// bool wwr[5001] = { 0 };
// wwr[z] = true;
// while (q.size())
// {
// int zz = q.front();
// q.pop();
// if (!wwr[zz])
// {
// ans.push_back(zz);
// wwr[zz] = true;
// if (++nn == 2)break;
// }
// for (int i = 1; i <= n; i++)
// {
// if (!wwr[i] && a[i][zz] == 1)
// {
// q.push(i);
// }
// }
// }
// if (ans.size() == 3)
// {
// if (ans[0] == 2793)cout <<sum<< endl;
// for (int i = 0; i < 3; i++)
// {
// cout << ans[i] << " ";
// }
// cout << endl;
// }
// else
// {
// cout << "NOT FOUND\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: 3756kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3780kb
input:
2 5 1 1
output:
1
result:
wrong answer 1st numbers differ - expected: '-1', found: '1'