Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
for i in range(n - 1):
if s[i] != s[i + 1]:
print(i + 1, i + 2)
break
else:
print(-1, -1)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
vector<int> id;
for (int i = 0; i < n; ++i) if (s[i] == '2')
id.push_back(i);
int k = id.size();
if (k == 1 || k == 2) {
cout << "NO\n";
continue;
}
vector<string> t(n, string(n, '='));
for (int i = 0; i < n; ++i) t[i][i] = 'X';
for (int i = 0; i < k; ++i) {
int x = id[i], y = id[(i + 1) % k];
t[x][y] = '+';
t[y][x] = '-';
}
cout << "YES\n";
for (int i = 0; i < n; ++i) cout << t[i] << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int mx = *max_element(a.begin(), a.end());
int cmx = count(a.begin(), a.end(), mx);
int k = count(a.begin(), a.end(), mx - 1);
int ans = 1, sub = 1;
for (long long i = 1; i <= n; ++i) {
ans = ans * i % MOD;
if (i != k + 1) sub = sub * i % MOD;
}
if (cmx == 1) ans = (ans - sub + MOD) % MOD;
cout << ans << '\n';
}
}
Idea: BledDest
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 all(a) (a).begin(), (a).end()
#define x first
#define y second
typedef long long li;
typedef pair<int, int> 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) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
int n, m, k;
vector<int> x, y;
vector<pt> ps;
inline bool read() {
if(!(cin >> n >> m >> k))
return false;
x.resize(n);
fore (i, 0, n)
cin >> x[i];
y.resize(m);
fore (i, 0, m)
cin >> y[i];
ps.resize(k);
fore (i, 0, k)
cin >> ps[i].x >> ps[i].y;
return true;
}
inline void solve() {
li ans = 0;
fore (_i, 0, 2) {
vector<int> cntY(m, 0);
sort(all(ps));
vector<pt> bord(k);
int u = 0;
while (u < k) {
int v = u;
while (v < k && ps[v].x == ps[u].x)
v++;
fore (i, u, v) {
int r = int(lower_bound(all(y), ps[i].y) - y.begin());
int l = r;
if (y[l] > ps[i].y)
l--;
assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
bord[i] = {l, r};
}
fore (i, u, v) if (bord[i].x < bord[i].y)
ans += cntY[bord[i].x];
fore (i, u, v) if (bord[i].x < bord[i].y)
cntY[bord[i].x]++;
u = v;
}
fore (i, 0, k)
swap(ps[i].x, ps[i].y);
swap(x, y);
swap(n, m);
}
cout << ans << 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);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
}
vector<int> evaluate(int n, int choice_mask)
{
int cur_place = n / 2 + 1;
int cur_bit = n - 2;
vector<int> p(n);
vector<int> c(n);
for(int i = 0; i < n; i++)
c[i] = i;
while(c.size() != 1)
{
vector<int> nc;
for(int i = 0; i < c.size(); i += 2)
{
if(choice_mask & (1 << cur_bit))
{
p[c[i]] = cur_place;
nc.push_back(c[i + 1]);
}
else
{
p[c[i + 1]] = cur_place;
nc.push_back(c[i]);
}
cur_bit--;
}
c = nc;
cur_place /= 2;
cur_place++;
}
p[c[0]] = 1;
return p;
}
vector<int> adjust(int n, vector<int> p, bool winning)
{
for(int i = 0; i < n; i++)
{
if(p[i] == 1)
{
if(!winning) p[i]++;
}
else
p[i] = p[i] * 2 - 1;
}
return p;
}
int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
{
if(partial)
p = adjust(n, p, winning);
int res = 0;
for(int i = 0; i < n; i++)
res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
return res;
}
int main()
{
int k, A, h;
cin >> k >> A >> h;
if(k <= 4)
{
for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
{
vector<int> p = evaluate(1 << k, i);
if(get_hash(1 << k, p, A) == h)
{
for(auto x : p) cout << x << " ";
cout << endl;
return 0;
}
}
}
else
{
int mask_left = -1;
int mask_right = -1;
bool left_win = false;
for(int c = 0; c < 2; c++)
{
map<int, int> left_map;
for(int i = 0; i < (1 << 16); i++)
{
vector<int> p = evaluate(16, i);
int left_hash = get_hash(16, p, A, true, c == 0, 0);
left_map[left_hash] = i;
}
for(int i = 0; i < (1 << 16); i++)
{
vector<int> p = evaluate(16, i);
int right_hash = get_hash(16, p, A, true, c == 1, 16);
int left_hash = add(h, MOD - right_hash);
if(left_map.count(left_hash))
{
mask_left = left_map[left_hash];
mask_right = i;
left_win = (c == 0);
}
}
}
if(mask_left != -1)
{
vector<int> ans_left = evaluate(16, mask_left);
vector<int> ans_right = evaluate(16, mask_right);
ans_left = adjust(16, ans_left, left_win);
ans_right = adjust(16, ans_right, !left_win);
for(auto x : ans_left)
cout << x << " ";
for(auto x : ans_right)
cout << x << " ";
return 0;
}
}
cout << -1 << endl;
return 0;
}
1569F - Palindromic Hamiltonian Path
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
vector<vector<char>> g;
map<long long, bool> dp;
void brute(int n, vector<int> &p){
int x = find(p.begin(), p.end(), -1) - p.begin();
if (x == int(p.size())){
vector<vector<char>> dp2(1 << n, vector<char>(n));
vector<int> pos1(n), pos2(n);
forn(i, p.size()){
pos1[p[i]] = pos2[p[i]];
pos2[p[i]] = i;
}
forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
forn(j, n) if (!((mask >> j) & 1)){
dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
}
}
forn(i, n) if (dp2[(1 << n) - 1][i]){
long long num = 0;
for (int x : p) num = num * 6 + x;
dp[num] = true;
break;
}
return;
}
for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
p[x] = p[y] = n;
brute(n + 1, p);
p[x] = p[y] = -1;
}
}
bool dfs(vector<int> p){
vector<int> used(int(p.size()), -1);
int cnt = 0;
forn(i, p.size()) if (used[p[i]] == -1)
used[p[i]] = cnt++;
long long num = 0;
for (int& x : p){
x = used[x];
num = num * 6 + x;
}
if (dp.count(num)) return dp[num];
bool res = false;
vector<int> cur(cnt);
forn(i, p.size()) ++cur[p[i]];
forn(i, p.size()) if (cur[p[i]] > 2){
int x = p[i];
for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
p[i] = p[j] = cnt;
if (dfs(p)){
res = true;
break;
}
p[i] = p[j] = x;
}
break;
}
return dp[num] = res;
}
void brute2(int n, vector<int> &p){
int x = find(p.begin(), p.end(), -1) - p.begin();
if (x == int(p.size())){
dfs(p);
return;
}
forn(i, n + 1){
for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
p[x] = p[y] = i;
brute2(max(n, i + 1), p);
p[x] = p[y] = -1;
}
}
}
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
g.resize(n, vector<char>(n));
forn(_, m){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v][u] = g[u][v] = 1;
}
vector<int> cur(n, -1);
brute(0, cur);
brute2(0, cur);
vector<long long> fact(k + 1);
fact[0] = 1;
for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
long long ans = 0;
for (auto it : dp) if (it.second){
long long num = it.first;
long long mx = 1;
while (num){
mx = max(mx, num % 6 + 1);
num /= 6;
}
if (mx <= k){
ans += fact[k] / fact[k - mx];
}
}
printf("%lld\n", ans);
return 0;
}