Idea: adedalic
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
if(n % 2 == 1):
print(7, end='')
n -= 3
while(n > 0):
print(1, end='')
n -= 2
print()
Idea: Roms
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
int n, x;
string s;
inline bool read() {
if(!(cin >> n >> x >> s))
return false;
return true;
}
inline void solve() {
int ans = 0;
bool infAns = false;
int cntZeros = (int)count(s.begin(), s.end(), '0');
int total = cntZeros - (n - cntZeros);
int bal = 0;
for(int i = 0; i < n; i++) {
if(total == 0) {
if(bal == x)
infAns = true;
}
else if(abs(x - bal) % abs(total) == 0) {
if((x - bal) / total >= 0)
ans++;
}
if(s[i] == '0')
bal++;
else
bal--;
}
if(infAns) 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--) {
read();
solve();
}
return 0;
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include<bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
const int INF = int(1e9) + 99;
int tc;
string s, t;
int nxt[N][26];
int main() {
cin >> tc;
while(tc--){
cin >> s >> t;
for(int i = 0; i < s.size() + 5; ++i)
for(int j = 0; j < 26; ++j)
nxt[i][j] = INF;
for(int i = int(s.size()) - 1; i >= 0; --i){
for(int j = 0; j < 26; ++j)
nxt[i][j] = nxt[i + 1][j];
nxt[i][s[i] - 'a'] = i;
}
int res = 1, pos = 0;
for(int i = 0; i < t.size(); ++i){
if(pos == s.size()){
pos = 0;
++res;
}
if(nxt[pos][t[i] - 'a'] == INF){
pos = 0;
++res;
}
if(nxt[pos][t[i] - 'a'] == INF && pos == 0){
res = INF;
break;
}
pos = nxt[pos][t[i] - 'a'] + 1;
}
if(res >= INF) cout << -1 << endl;
else cout << res << endl;
}
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun gcd(a : Long, b : Long) : Long {
return if (a == 0L) b else gcd(b % a, a)
}
fun phi(a : Long) : Long {
var (tmp, ans) = listOf(a, a)
var d = 2L
while (d * d <= tmp) {
var cnt = 0
while (tmp % d == 0L) {
tmp /= d
cnt++
}
if (cnt > 0) ans -= ans / d
d++
}
if (tmp > 1L) ans -= ans / tmp
return ans
}
fun main() {
val t = readLine()!!.toInt()
for (tc in 1..t) {
val (a, m) = readLine()!!.split(' ').map { it.toLong() }
println(phi(m / gcd(a, m)))
}
}
1295E - Permutation Separation
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
int n;
int p[N];
int rp[N];
int a[N];
long long b[N];
long long t[4 * N];
long long add[4 * N];
void build(int v, int l, int r){
if(r - l == 1){
t[v] = b[l];
return;
}
int mid = (l + r) / 2;
build(v * 2 + 1, l, mid);
build(v * 2 + 2, mid, r);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
void push(int v, int l, int r){
if(add[v] != 0){
if(r - l > 1)
for(int i = v+v+1; i < v+v+3; ++i){
add[i] += add[v];
t[i] += add[v];
}
add[v] = 0;
}
}
void upd(int v, int l, int r, int L, int R, int x){
if(L >= R) return;
if(l == L && r == R){
add[v] += x;
t[v] += x;
push(v, l, r);
return;
}
push(v, l, r);
int mid = (l + r) / 2;
upd(v * 2 + 1, l, mid, L, min(mid, R), x);
upd(v * 2 + 2, mid, r, max(mid, L), R, x);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
void upd(int l, int r, int x){
upd(0, 0, n, l, r, x);
}
long long get(int v, int l, int r, int L, int R){
if(L >= R) return 1e18;
push(v, l, r);
if(l == L && r == R)
return t[v];
int mid = (l + r) / 2;
return min(get(v * 2 + 1, l, mid, L, min(R, mid)),
get(v * 2 + 2, mid, r, max(L, mid), R));
}
long long get(int l, int r){
return get(0, 0, n, l, r);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", p + i);
--p[i];
rp[p[i]] = i;
}
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
b[0] = a[0];
for(int i = 1; i < n; ++i)
b[i] = a[i] + b[i - 1];
build(0, 0, n);
long long res = get(0, n - 1);
//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
for(int i = 0; i < n; ++i){
int pos = rp[i];
upd(pos, n, -a[pos]);
upd(0, pos, a[pos]);
res = min(res, get(0, n - 1));
//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
}
cout << res << endl;
return 0;
}
Idea: Roms
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;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
typedef vector<int> poly;
void norm(poly& p)
{
while(p.size() > 0 && p.back() == 0)
p.pop_back();
}
poly operator +(const poly& a, const poly& b)
{
poly c = a;
while(c.size() < b.size()) c.push_back(0);
for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]);
norm(c);
return c;
}
poly operator +(const poly& a, int b)
{
return a + poly(1, b);
}
poly operator +(int a, const poly& b)
{
return b + a;
}
poly operator *(const poly& a, int b)
{
poly c = a;
for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b);
norm(c);
return c;
}
poly operator /(const poly& a, int b)
{
return a * inv(b);
}
poly operator *(const poly& a, const poly& b)
{
poly c(a.size() + b.size() - 1);
for(int i = 0; i < a.size(); i++)
for(int j = 0; j < b.size(); j++)
c[i + j] = add(c[i + j], mul(a[i], b[j]));
norm(c);
return c;
}
poly interpolate(const vector<int>& x, const vector<int>& y)
{
int n = int(x.size()) - 1;
vector<vector<int> > f(n + 1);
f[0] = y;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= n - i; j++)
f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j])));
poly cur = poly(1, 1);
poly res;
for(int i = 0; i <= n; i++)
{
res = res + cur * f[i][0];
cur = cur * poly({add(0, -x[i]), 1});
}
return res;
}
int eval(const poly& a, int x)
{
int res = 0;
for(int i = int(a.size()) - 1; i >= 0; i--)
res = add(mul(res, x), a[i]);
return res;
}
poly sumFromL(const poly& a, int L, int n)
{
vector<int> x;
for(int i = 0; i <= n; i++)
x.push_back(L + i);
vector<int> y;
int cur = 0;
for(int i = 0; i <= n; i++)
{
cur = add(cur, eval(a, x[i]));
y.push_back(cur);
}
return interpolate(x, y);
}
int sumOverSegment(const poly& a, int L, int R)
{
return eval(sumFromL(a, L, a.size()), R - 1);
}
int main() {
int n;
cin >> n;
vector<int> L(n), R(n);
for(int i = 0; i < n; i++)
{
cin >> L[i] >> R[i];
R[i]++;
}
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
vector<int> coord = {0, MOD - 2};
for(int i = 0; i < n; i++)
{
coord.push_back(L[i]);
coord.push_back(R[i]);
}
sort(coord.begin(), coord.end());
coord.erase(unique(coord.begin(), coord.end()), coord.end());
vector<int> cL = coord, cR = coord;
cL.pop_back();
cR.erase(cR.begin());
int cnt = coord.size() - 1;
vector<poly> cur(cnt);
for(int i = 0; i < cnt; i++)
if(cL[i] >= L[0] && cR[i] <= R[0])
cur[i] = poly(1, inv(R[0] - L[0]));
for(int i = 1; i < n; i++)
{
vector<poly> nxt(cnt);
int curSum = 0;
for(int j = 0; j < cnt; j++)
{
nxt[j] = sumFromL(cur[j], cL[j], i) + curSum;
curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j]));
}
for(int j = 0; j < cnt; j++)
nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0);
cur = nxt;
}
int ans = 0;
for(int i = 0; i < cnt; i++)
ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i]));
cout << ans << endl;
}