Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int T;
cin >> T;
int n;
string s;
forn(_, T){
cin >> n >> s;
bool ok = true;
forn(i, n){
int k = abs(s[i] - s[n - i - 1]);
if (k > 2 || k % 2 == 1){
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << endl;
}
return 0;
}
1027B - Numbers on the Chessboard
Tutorial
Tutorial is loading...
Solution (Vovuh)
import sys
lst = sys.stdin.readlines()
n, q = map(int, lst[0].split())
for i in range(q):
x, y = map(int, lst[i + 1].split())
cnt = (x - 1) * n + y
ans = (cnt + 1) // 2
if ((x + y) % 2 == 1): ans += (n * n + 1) // 2
sys.stdout.write(str(ans) + '\n')
1027C - Minimum Value Rectangle
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
using namespace std;
const int N = 1000 * 1000 + 13;
int n, m;
int a[N];
int b[N];
int main() {
int T;
scanf("%d", &T);
forn(_, T){
scanf("%d", &n);
forn(i, n)
scanf("%d", &a[i]);
sort(a, a + n);
m = 0;
forn(i, n - 1){
if (a[i] == a[i + 1]){
b[m++] = a[i];
++i;
}
}
int A = b[0], B = b[1];
li P2 = (A + B) * li(A + B);
li S = A * li(B);
forn(i, m - 1){
li p2 = (b[i] + b[i + 1]) * li(b[i] + b[i + 1]);
li s = b[i] * li(b[i + 1]);
if (s * P2 > S * p2){
A = b[i];
B = b[i + 1];
S = s;
P2 = p2;
}
}
printf("%d %d %d %d\n", A, A, B, B);
}
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
forn(i, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
vector<int> a, c;
inline bool read() {
if(!(cin >> n))
return false;
c.assign(n, 0);
a.assign(n, 0);
forn(i, n)
assert(scanf("%d", &c[i]) == 1);
forn(i, n) {
assert(scanf("%d", &a[i]) == 1);
a[i]--;
}
return true;
}
vector< vector<int> > cycles;
vector<char> used;
vector<int> path;
void dfs(int v) {
path.push_back(v);
used[v] = 1;
int to = a[v];
if(used[to] != 2) {
if(used[to] == 1) {
cycles.emplace_back();
int id = sz(path) - 1;
while(path[id] != to)
cycles.back().push_back(path[id--]);
cycles.back().push_back(to);
} else
dfs(to);
}
path.pop_back();
used[v] = 2;
}
inline void solve() {
used.assign(n, 0);
forn(i, n) {
if (!used[i])
dfs(i);
}
li ans = 0;
for(auto &cur : cycles) {
int mn = c[cur[0]];
for(int v : cur)
mn = min(mn, c[v]);
ans += mn;
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike) O(n^3)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 500 + 7;
const int MOD = 998244353;
int n, k;
int dp[2][N][N];
int cnt[N];
int pr[N];
void add(int &a, int b){
a += b;
if (a >= MOD)
a -= MOD;
}
int main() {
scanf("%d%d", &n, &k);
dp[0][0][0] = 1;
forn(ii, n){
int i = ii & 1;
int ni = i ^ 1;
memset(dp[ni], 0, sizeof(dp[ni]));
forn(j, n + 1){
forn(k, n + 1){
add(dp[ni][j + 1][max(j + 1, k)], dp[i][j][k]);
add(dp[ni][1][max(1, k)], dp[i][j][k]);
}
}
}
forn(i, n + 1)
forn(j, n + 1)
add(cnt[i], dp[n & 1][j][i]);
forn(i, n + 1){
add(pr[i + 1], pr[i]);
add(pr[i + 1], cnt[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
add(ans, cnt[i] * (long long)(pr[min(n + 1, (k - 1) / i + 1)]) % MOD);
ans = (ans * (long long)((MOD + 1) / 2)) % MOD;
printf("%d\n", ans);
return 0;
}
Solution (BledDest) O(n^2)
def norm(x):
return (x % 998244353 + 998244353) % 998244353
n, k = map(int, input().split())
dp1 = [0]
dp2 = [0]
for i in range(n):
l = [1]
cur = 0
for j in range(n + 1):
cur += l[j]
if(j > i):
cur -= l[j - i - 1]
cur = norm(cur)
l.append(cur)
dp1.append(l[n])
dp2.append(norm(dp1[i + 1] - dp1[i]))
ans = 0
for i in range(n + 1):
for j in range(n + 1):
if(i * j < k):
ans = norm(ans + dp2[i] * dp2[j])
ans = norm(ans * 2)
print(ans)
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 2 * 1000 * 1000 + 11;
const int INF = 1e9 + 1;
int n;
int a[N][2];
vector<int> s;
bool used[N];
bool exam[N];
vector<pair<int, int>> g[N];
bool deny(int v) {
if (used[v]) return false;
used[v] = true;
for (auto it : g[v]) {
int to = it.first;
int ex = it.second;
if (exam[ex]) continue;
if (used[to])
return false;
exam[ex] = true;
if (!deny(to))
return false;
}
return true;
}
int cntv, cnte;
void dfs(int v) {
++cntv;
used[v] = true;
for (auto it : g[v]) {
int to = it.first;
int ex = it.second;
if (exam[ex]) continue;
exam[ex] = true;
++cnte;
if (!used[to])
dfs(to);
}
}
bool check(int day) {
memset(used, false, sizeof(used));
memset(exam, false, sizeof(exam));
forn(i, s.size()) if (i > day) {
if (!deny(i)) {
return false;
}
}
forn(i, s.size()) {
if (!used[i]) {
cntv = 0;
cnte = 0;
dfs(i);
if (cntv < cnte)
return false;
}
}
return true;
}
int main() {
scanf("%d", &n);
forn(i, n) forn(j, 2) {
scanf("%d", &a[i][j]);
s.push_back(a[i][j]);
}
sort(s.begin(), s.end());
s.resize(unique(s.begin(), s.end()) - s.begin());
forn(i, n) {
forn(j, 2) {
a[i][j] = lower_bound(s.begin(), s.end(), a[i][j]) - s.begin();
}
g[a[i][0]].push_back(make_pair(a[i][1], i));
g[a[i][1]].push_back(make_pair(a[i][0], i));
}
int l = 0, r = int(s.size()) - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
for (int i = l; i <= r; ++i) {
if (check(i)) {
printf("%d\n", s[i]);
return 0;
}
}
puts("-1");
}
Solution (Vovuh) Kuhn's Algorithm
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(NULL));
const int N = 2 * 1000 * 1000 + 11;
const int INF = 1e9;
int n;
int a[N][2];
vector<int> nums;
int m;
vector<int> g[N];
int mt[N];
int used[N];
int T = 1;
bool try_kuhn(int v) {
if (used[v] == T)
return false;
used[v] = T;
for (auto to : g[v]) {
if (mt[to] == -1) {
mt[to] = v;
return true;
}
}
for (auto to : g[v]) {
if (try_kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
scanf("%d", &a[i][j]);
nums.push_back(a[i][j]);
}
}
sort(nums.begin(), nums.end());
nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
m = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
a[i][j] = lower_bound(nums.begin(), nums.end(), a[i][j]) - nums.begin();
}
}
for (int i = 0; i < n; ++i) {
g[a[i][0]].push_back(i);
g[a[i][1]].push_back(i);
}
memset(mt, -1, sizeof(mt));
int match = 0;
for (int i = 0; i < m; ++i) {
if (try_kuhn(i)) {
++T;
++match;
if (match == n) {
printf("%d\n", nums[i]);
return 0;
}
}
}
puts("-1");
return 0;
}
Tutorial
Tutorial is loading...
Solution (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())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
li m, x;
inline bool read() {
if(!(cin >> m >> x))
return false;
return true;
}
map< li, vector<pt> > dFact;
vector<pt> fact(li v) {
if(dFact.count(v))
return dFact[v];
li oldv = v;
vector<pt> fs;
for(li d = 2; d * d <= v; d++) {
int cnt = 0;
while(v % d == 0)
v /= d, cnt++;
if(cnt > 0)
fs.emplace_back(d, cnt);
}
if(v > 1)
fs.emplace_back(v, 1), v = 1;
return dFact[oldv] = fs;
}
vector<pt> merge(const vector<pt> &a, const vector<pt> &b) {
vector<pt> ans;
int u = 0, v = 0;
while(u < sz(a) && v < sz(b)) {
if(a[u].x < b[v].x)
ans.push_back(a[u++]);
else if(a[u].x > b[v].x)
ans.push_back(b[v++]);
else {
ans.emplace_back(a[u].x, a[u].y + b[v].y);
u++, v++;
}
}
while(u < sz(a))
ans.push_back(a[u++]);
while(v < sz(b))
ans.push_back(b[v++]);
return ans;
}
li getPw(li a, li b) {
li ans = 1;
fore(i, 0, b)
ans *= a;
return ans;
}
li mul(li a, li b, li mod) {
li m = li(ld(a) * b / mod);
li rem = a * b - m * mod;
while(rem < 0)
rem += mod;
while(rem >= mod)
rem -= mod;
return rem;
}
li binPow(li a, li k, li mod) {
li ans = 1 % mod;
while(k > 0) {
if(k & 1)
ans = mul(ans, a, mod);
a = mul(a, a, mod);
k >>= 1;
}
return ans;
}
li findOrder(li x, li mod, const vector<pt> &f) {
li phi = 1;
fore(i, 0, sz(f)) fore(k, 0, f[i].y)
phi *= f[i].x;
if(phi == 1 || x == 0)
return 1;
li ord = 1;
fore(i, 0, sz(f)) {
li basePw = phi;
fore(k, 0, f[i].y)
basePw /= f[i].x;
li curV = binPow(x, basePw, mod);
int curPw = -1;
fore(k, 0, f[i].y + 1) {
if(curV != 1)
curPw = k;
curV = binPow(curV, f[i].x, mod);
}
ord *= getPw(f[i].x, curPw + 1);
}
return ord;
}
vector<pt> fm;
vector<int> pw;
li calc(int pos, li dv) {
if(pos >= sz(fm)) {
vector<pt> cf = fm;
fore(i, 0, sz(fm))
cf[i].y = max(pw[i] - 1, 0);
li phi = dv;
fore(i, 0, sz(fm)) {
if(pw[i] > 0) {
cf = merge(cf, fact(fm[i].x - 1));
phi -= phi / fm[i].x;
}
}
li k = findOrder(x % dv, dv, cf);
return phi / k;
}
li ans = 0;
fore(i, 0, fm[pos].y + 1) {
pw[pos] = i;
ans += calc(pos + 1, dv);
dv *= fm[pos].x;
}
return ans;
}
inline void solve() {
fm = fact(m);
pw.assign(sz(fm), 0);
li ans = calc(0, 1);
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}