Идея: Roms
Разбор
Tutorial is loading...
Решение (adedalic)
import kotlin.math.abs
fun main() {
val q = readLine()!!.toInt()
for (ct in 1..q) {
val (n, x, a, b) = readLine()!!.split(' ').map { it.toInt() }
println(minOf(n - 1, abs(a - b) + x))
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x, y;
cin >> x >> y;
if (x > 3) puts("YES");
else if (x == 1) puts(y == 1 ? "YES" : "NO");
else puts(y <= 3 ? "YES" : "NO");
}
int main() {
int tc;
cin >> tc;
while (tc--) solve();
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
for(int i = 0; i < n; i++)
cin >> a[i];
return true;
}
inline void solve() {
int ans = n + 5;
vector<int> lst(n + 1, -1);
for(int i = 0; i < n; i++) {
if(lst[a[i]] != -1)
ans = min(ans, i - lst[a[i]] + 1);
lst[a[i]] = i;
}
if(ans > n)
ans = -1;
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
assert(read());
solve();
}
return 0;
}
1257D - Yet Another Monster Killing Problem
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
int t;
int n;
int a[N];
int m;
int p[N], s[N];
int bst[N];
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i <= n; ++i) bst[i] = 0;
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
scanf("%d", &m);
for(int i = 0; i < m; ++i){
scanf("%d %d", p + i, s + i);
bst[s[i]] = max(bst[s[i]], p[i]);
}
for(int i = n - 1; i >= 0; --i)
bst[i] = max(bst[i], bst[i + 1]);
int pos = 0;
int res = 0;
bool ok = true;
while(pos < n){
++res;
int npos = pos;
int mx = 0;
while(true){
mx = max(mx, a[npos]);
if(mx > bst[npos - pos + 1]) break;
++npos;
}
if(pos == npos){
ok = false;
break;
}
pos = npos;
}
if(!ok) res = -1;
printf("%d\n", res);
}
return 0;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int k1, k2, k3;
scanf("%d %d %d", &k1, &k2, &k3);
int n = k1 + k2 + k3;
vector<int> a(n);
for(int i = 0; i < k1; i++)
{
int x;
scanf("%d", &x);
a[x - 1] = 0;
}
for(int i = 0; i < k2; i++)
{
int x;
scanf("%d", &x);
a[x - 1] = 1;
}
for(int i = 0; i < k3; i++)
{
int x;
scanf("%d", &x);
a[x - 1] = 2;
}
int ans = 0;
int bestp = 0;
for(int i = 0; i < n; i++)
if(a[i] != 2)
ans++;
vector<int> cntl(3);
vector<int> cntr(3);
for(int i = 0; i < n; i++)
cntr[a[i]]++;
for(int i = 0; i < n; i++)
{
cntl[a[i]]++;
cntr[a[i]]--;
bestp = max(bestp, cntl[0] - cntl[1]);
int curans = cntr[0] + cntr[1] + cntl[2] + cntl[0] - bestp;
ans = min(ans, curans);
}
cout << ans << endl;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int N = 143;
const int K = 15;
const int V = 5000000;
int n;
li a[N];
int lst[V];
map<int, int> nxt[V];
int t = 1;
li a1[N];
li a2[N];
int get_nxt(int v, int x)
{
if(!nxt[v].count(x))
nxt[v][x] = t++;
return nxt[v][x];
}
void add(vector<int> diff, int x)
{
int v = 0;
for(auto i : diff)
v = get_nxt(v, i);
lst[v] = x;
}
int try_find(vector<int> diff)
{
int v = 0;
for(auto i : diff)
{
if(!nxt[v].count(i))
return -1;
v = nxt[v][i];
}
return lst[v];
}
vector<int> get_diff(li arr[N], int x)
{
vector<int> cnt(n);
for(int i = 0; i < n; i++)
cnt[i] = __builtin_popcountll(arr[i] ^ x);
vector<int> diff(n - 1);
for(int i = 0; i + 1 < n; i++)
diff[i] = cnt[i + 1] - cnt[0];
return diff;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
{
a1[i] = (a[i] >> K);
a2[i] = a[i] ^ (a1[i] << K);
}
for(int i = 0; i < (1 << K); i++)
{
vector<int> d = get_diff(a1, i);
add(d, i);
}
for(int i = 0; i < (1 << K); i++)
{
vector<int> d = get_diff(a2, i);
for(int j = 0; j + 1 < n; j++)
d[j] *= -1;
int x = try_find(d);
if(x != -1)
{
li res = (li(x) << K) ^ i;
cout << res << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int LOGN = 18;
const int MOD = 998244353;
int g = 3;
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int norm(int a) {
while(a >= MOD) a -= MOD;
while(a < 0) a += MOD;
return a;
}
int binPow (int a, int k) {
int ans = 1;
for (; k > 0; k >>= 1) {
if (k & 1)
ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
int inv(int a) {
return binPow(a, MOD - 2);
}
vector<int> w[LOGN], rv;
bool precalced = false;
void precalc() {
if(precalced)
return;
precalced = true;
int wb = binPow(g, (MOD - 1) / (1 << LOGN));
fore(st, 0, LOGN) {
w[st].assign(1 << st, 1);
int bw = binPow(wb, 1 << (LOGN - st - 1));
int cw = 1;
fore(k, 0, (1 << st)) {
w[st][k] = cw;
cw = mul(cw, bw);
}
}
rv.assign(1 << LOGN, 0);
fore(i, 1, sz(rv))
rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
const int MX = (1 << LOGN) + 3;
inline void fft(int a[MX], int n, bool inverse) {
precalc();
int ln = __builtin_ctz(n);
assert((1 << ln) < MX);
assert((1 << ln) == n);
fore(i, 0, n) {
int ni = rv[i] >> (LOGN - ln);
if(i < ni) swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++) {
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1)) {
fore(pos, k, k + len) {
int l = a[pos];
int r = mul(a[pos + len], w[st][pos - k]);
a[pos] = norm(l + r);
a[pos + len] = norm(l - r);
}
}
}
if(inverse) {
int in = inv(n);
fore(i, 0, n)
a[i] = mul(a[i], in);
reverse(a + 1, a + n);
}
}
int aa[MX], bb[MX], cc[MX];
vector<int> multiply(const vector<int> &a, const vector<int> &b) {
int ln = 1;
while(ln < (sz(a) + sz(b)))
ln <<= 1;
fore(i, 0, ln)
aa[i] = (i < sz(a) ? a[i] : 0);
fore(i, 0, ln)
bb[i] = (i < sz(b) ? b[i] : 0);
fft(aa, ln, false);
fft(bb, ln, false);
fore(i, 0, ln)
cc[i] = mul(aa[i], bb[i]);
fft(cc, ln, true);
vector<int> ans(cc, cc + ln);
while(ans.back() == 0)
ans.pop_back();
return ans;
}
int n;
vector<int> ps;
inline bool read() {
if(!(cin >> n))
return false;
ps.resize(n);
fore(i, 0, n)
cin >> ps[i];
return true;
}
struct cmp {
bool operator ()(const vector<int> &a, const vector<int> &b) {
return sz(a) < sz(b);
}
};
inline void solve() {
map<int, int> cnt;
fore (i, 0, n)
cnt[ps[i]]++;
multiset< vector<int>, cmp > polys;
for (auto p : cnt)
polys.emplace(p.second + 1, 1);
while (sz(polys) > 1) {
auto it2 = polys.begin();
auto it1 = it2++;
polys.insert(multiply(*it1, *it2));
polys.erase(it1);
polys.erase(it2);
}
auto poly = *polys.begin();
// cerr << '[';
// fore(i, 0, sz(poly)) {
// if(i) cerr << ", ";
// cerr << poly[i];
// }
// cerr << ']' << endl;
cout << poly[n / 2] << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}