Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
readLine()!!.toInt()
println(readLine()!!.split(' ').count { it != "2" })
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for t in range(int(input())):
a, b, c = map(int, input().split())
print("1" + "0" * (a - 1), "1" * (b - c + 1) + "0" * (c - 1))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d%d", &n, &q);
vector<int> a(n);
for (int& x : a) scanf("%d", &x);
while (q--) {
int x;
scanf("%d", &x);
int p = find(a.begin(), a.end(), x) - a.begin();
printf("%d ", p + 1);
rotate(a.begin(), a.begin() + p, a.begin() + p + 1);
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int n, k;
int cur[26];
vector<int> path;
void dfs(int v) {
while (cur[v] < k) {
int u = cur[v]++;
dfs(u);
path.push_back(u);
}
}
int main() {
scanf("%d%d", &n, &k);
dfs(0);
printf("a");
for (int i = 0; i < n - 1; ++i)
printf("%c", path[i % path.size()] + 'a');
}
1511E - Colorings and Dominoes
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 300043;
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 sub(int x, int y)
{
return add(x, MOD - y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1)
z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
string s[N];
int p[N];
int n, m;
char buf[N];
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%s", buf);
s[i] = buf;
}
p[0] = divide(1, 2);
for(int i = 1; i < N; i++)
if(i % 2 == 1)
p[i] = sub(p[i - 1], divide(1, binpow(2, i)));
else
p[i] = add(p[i - 1], divide(1, binpow(2, i)));
int ans = 0;
int w = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(s[i][j] != '*')
w = add(w, 1);
for(int i = 0; i < n; i++)
{
int c = 0;
for(int j = 0; j < m; j++)
{
if(s[i][j] == '*')
c = 0;
else
c++;
if(c > 0)
ans = add(ans, p[c]);
}
}
for(int j = 0; j < m; j++)
{
int c = 0;
for(int i = 0; i < n; i++)
{
if(s[i][j] == '*')
c = 0;
else
c++;
if(c > 0)
ans = add(ans, p[c]);
}
}
ans = mul(ans, binpow(2, w));
cout << ans << endl;
}
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;
const int MOD = 998244353;
const int K = 161;
const int AL = 26;
struct node{
int nxt[AL];
bool term;
node(){
memset(nxt, -1, sizeof(nxt));
term = false;
};
int& operator [](const int x){
return nxt[x];
}
};
vector<node> trie;
int tot;
void add(const string &s){
int cur = 0;
int d = 1;
for (const char &c : s){
++d;
if (trie[cur][c - 'a'] == -1){
trie[cur][c - 'a'] = trie.size();
trie.push_back(node());
tot += d;
}
cur = trie[cur][c - 'a'];
}
trie[cur].term = true;
}
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
typedef array<array<int, K>, K> mat;
mat operator *(const mat &a, const mat &b){
mat c;
forn(i, K) forn(j, K) c[i][j] = 0;
forn(i, K) forn(j, K) forn(k, K)
c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
return c;
}
mat binpow(mat a, long long b){
mat res;
forn(i, K) forn(j, K) res[i][j] = i == j;
while (b){
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
map<pair<int, int>, int> num;
queue<pair<int, int>> q;
int get(int v, int u){
if (v > u) swap(v, u);
if (!num.count({v, u})){
int k = num.size();
assert(k < K);
num[{v, u}] = k;
q.push({v, u});
}
return num[{v, u}];
}
int main() {
int n;
long long m;
cin >> n >> m;
trie = vector<node>(1, node());
tot = 1;
forn(i, n){
string s;
cin >> s;
add(s);
}
q.push({0, 0});
num[q.front()] = 0;
mat init;
forn(i, K) forn(j, K) init[i][j] = 0;
while (!q.empty()){
int v = q.front().first;
int u = q.front().second;
q.pop();
int x = get(v, u);
forn(c, AL){
int tov = trie[v][c];
int tou = trie[u][c];
if (tov == -1 || tou == -1) continue;
++init[x][get(tov, tou)];
if (trie[tov].term) ++init[x][get(0, tou)];
if (trie[tou].term) ++init[x][get(tov, 0)];
if (trie[tov].term && trie[tou].term) ++init[x][0];
}
}
init = binpow(init, m);
printf("%d\n", init[0][0]);
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 200043;
const int K = 10;
const int Z = 1 << K;
int rem[Z];
int t[N];
int get(int r)
{
int result = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
result ^= t[r];
return result;
}
void change(int i, int delta)
{
for (; i < N; i = (i | (i + 1)))
t[i] ^= delta;
}
int get(int l, int r)
{
return get(r) - get(l - 1);
}
int ans[N];
int c[N];
int cnt[N];
int n, m;
int ls[N];
int rs[N];
vector<int> qs[N];
vector<int> qs2[N];
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%d", &c[i]);
cnt[c[i]]++;
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int l, r;
scanf("%d %d", &l, &r);
ls[i] = l;
rs[i] = r;
qs[l].push_back(i);
qs2[r + 1].push_back(i);
}
for(int i = m; i >= 1; i--)
{
for(int j = 0; j < cnt[i]; j++)
{
rem[i % (1 << K)]++;
int r = i;
while(true)
{
int l = r - Z + 1;
l = max(1, l);
if(l > r)
break;
int diff = i - l;
diff >>= K;
change(l, diff);
change(r + 1, diff);
r -= Z;
}
}
for(auto x : qs[i])
{
int cur = (get(i)) << K;
for(int k = 0; k < Z; k++)
{
int dist = (k - i) % Z;
if(dist < 0)
dist += Z;
if(rem[k] & 1)
cur ^= dist;
}
ans[x] ^= cur;
}
for(auto x : qs2[i])
{
int cur = (get(ls[x])) << K;
for(int k = 0; k < Z; k++)
{
int dist = (k - ls[x]) % Z;
if(dist < 0)
dist += Z;
if(rem[k] & 1)
cur ^= dist;
}
ans[x] ^= cur;
}
}
for(int i = 0; i < q; i++)
if(ans[i] == 0)
printf("B");
else
printf("A");
}