Idea: vovuh
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", H"r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int tc;
cin >> tc;
while (tc--) {
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
}
cout << max(0, sum - m) << endl;
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
vector<long long> p(n), s(n + 1);
for (auto& x : p) cin >> x;
sort(p.begin(), p.end());
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + p[i];
while (q--) {
int x, y;
cin >> x >> y;
cout << s[n - x + y] - s[n - x] << '\n';
}
}
1697C - awoo's Favorite Problem
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
t = input()
if s.count('b') != t.count('b'):
print("NO")
continue
j = 0
for i in range(n):
if s[i] == 'b':
continue
while t[j] == 'b':
j += 1
if s[i] != t[j] or (s[i] == 'a' and i > j) or (s[i] == 'c' and i < j):
print("NO")
break
j += 1
else:
print("YES")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
char ask_character(int i)
{
cout << "? 1 " << i << endl;
cout.flush();
string s;
cin >> s;
return s[0];
}
int ask_cnt(int l, int r)
{
cout << "? 2 " << l << " " << r << endl;
cout.flush();
int x;
cin >> x;
return x;
}
int main()
{
int n;
cin >> n;
string s = "";
vector<vector<int>> cnt(n + 1);
for(int i = 0; i < n; i++)
{
if(i == 0)
{
s.push_back(ask_character(1));
cnt[0] = {1};
}
else
{
int cur = ask_cnt(1, i + 1);
if(cur > cnt[i - 1][0])
s.push_back(ask_character(i + 1));
else
{
map<char, int> last;
for(int j = 0; j < s.size(); j++)
last[s[j]] = j;
vector<int> lasts;
for(auto x : last) lasts.push_back(x.second);
sort(lasts.begin(), lasts.end());
int l = 0;
int r = lasts.size();
// there is always an occurrence in [lasts[l], i)
// there is no occurrence in [lasts[r], i)
while(r - l > 1)
{
int m = (l + r) / 2;
int c = ask_cnt(lasts[m] + 1, i + 1);
if (c == cnt[i - 1][lasts[m]])
l = m;
else
r = m;
}
s.push_back(s[lasts[l]]);
}
cnt[i].resize(i + 1);
set<char> q;
for(int j = i; j >= 0; j--)
{
q.insert(s[j]);
cnt[i][j] = q.size();
}
}
}
cout << "! " << s << endl;
cout.flush();
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 143;
const int K = 5;
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 > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int fact[N];
int rfact[N];
int A(int n, int k)
{
return mul(fact[n], rfact[n - k]);
}
int n;
vector<int> g[N];
int x[N];
int y[N];
int dist[N][N];
int color[N];
int dp[N][N];
int cc = 0;
set<int> pts;
vector<int> compsize;
void dfs1(int i)
{
//cerr << i << endl;
if(pts.count(i) == 1) return;
pts.insert(i);
for(auto v : g[i])
{
dfs1(v);
}
}
void dfs2(int i, int c)
{
if(color[i] == c) return;
color[i] = c;
for(auto v : g[i])
dfs2(v, c);
}
int main()
{
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(i, fact[i - 1]);
for(int i = 0; i < N; i++)
rfact[i] = binpow(fact[i], MOD - 2);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d %d", &x[i], &y[i]);
}
for(int i = 0; i < n; i++)
{
dist[i][i] = int(1e9);
for(int j = 0; j < n; j++)
if(i != j)
dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
for(int i = 0; i < n; i++)
{
int d = *min_element(dist[i], dist[i] + n);
for(int j = 0; j < n; j++)
if(dist[i][j] == d) g[i].push_back(j);
}
for(int i = 0; i < n; i++)
{
if(color[i] != 0) continue;
cc++;
pts.clear();
dfs1(i);
//cerr << "!" << endl;
int d = *min_element(dist[i], dist[i] + n);
set<int> pts2 = pts;
bool bad = false;
for(auto x : pts)
for(auto y : pts2)
if(x != y && dist[x][y] != d)
bad = true;
if(bad)
{
color[i] = cc;
compsize.push_back(1);
}
else
{
dfs2(i, cc);
compsize.push_back(pts.size());
}
}
dp[0][0] = 1;
int m = compsize.size();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(dp[i][j] == 0) continue;
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
if(compsize[i] != 1)
{
dp[i + 1][j + compsize[i]] = add(dp[i + 1][j + compsize[i]], dp[i][j]);
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
ans = add(ans, mul(dp[m][i], A(n, i)));
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;
struct constraint{
int tp, i, j, x;
};
vector<vector<int>> g, tg;
vector<char> used;
vector<int> clr, ord;
void ts(int v){
used[v] = true;
for (int u : g[v]) if (!used[u])
ts(u);
ord.push_back(v);
}
void dfs(int v, int k){
clr[v] = k;
for (int u : tg[v]) if (clr[u] == -1)
dfs(u, k);
}
void either(int x, int y){
g[x ^ 1].push_back(y);
g[y ^ 1].push_back(x);
tg[y].push_back(x ^ 1);
tg[x].push_back(y ^ 1);
}
void implies(int x, int y){
either(x ^ 1, y);
}
void must(int x){
either(x, x);
}
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vector<constraint> c(m);
forn(i, m){
scanf("%d%d", &c[i].tp, &c[i].i);
if (c[i].tp != 1) scanf("%d", &c[i].j);
scanf("%d", &c[i].x);
--c[i].i, --c[i].j;
}
int vts = n * (k + 2);
g.assign(2 * vts, vector<int>());
tg.assign(2 * vts, vector<int>());
forn(i, n){
forn(j, (k + 2) - 1)
implies(2 * (i * (k + 2) + j + 1) + 1, 2 * (i * (k + 2) + j) + 1);
must(2 * (i * (k + 2) + 1) + 1);
must(2 * (i * (k + 2) + k + 1));
}
forn(i, n - 1) forn(j, k + 2){
implies(2 * (i * (k + 2) + j) + 1, 2 * ((i + 1) * (k + 2) + j) + 1);
}
forn(i, m){
if (c[i].tp == 1)
either(2 * (c[i].i * (k + 2) + c[i].x + 1) + 1, 2 * (c[i].i * (k + 2) + c[i].x));
else if (c[i].tp == 2){
for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
implies(2 * (c[i].i * (k + 2) + a) + 1, 2 * (c[i].j * (k + 2) + (c[i].x - a) + 1));
implies(2 * (c[i].j * (k + 2) + a) + 1, 2 * (c[i].i * (k + 2) + (c[i].x - a) + 1));
}
}
else{
for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
implies(2 * (c[i].i * (k + 2) + a + 1), 2 * (c[i].j * (k + 2) + (c[i].x - a)) + 1);
implies(2 * (c[i].j * (k + 2) + a + 1), 2 * (c[i].i * (k + 2) + (c[i].x - a)) + 1);
}
}
}
used.assign(2 * vts, 0);
ord.clear();
forn(i, used.size()) if (!used[i]) ts(i);
reverse(ord.begin(), ord.end());
clr.assign(2 * vts, -1);
int cc = 0;
for (int v : ord) if (clr[v] == -1){
dfs(v, cc);
++cc;
}
vector<int> vals(vts);
bool ans = true;
forn(i, vts){
if (clr[2 * i] == clr[2 * i + 1]){
ans = false;
break;
}
vals[i] = (clr[2 * i] < clr[2 * i + 1]);
}
if (!ans){
puts("-1");
continue;
}
forn(i, n){
int lst = 0;
forn(j, k + 2) if (vals[i * (k + 2) + j])
lst = j;
printf("%d ", lst);
}
puts("");
}
return 0;
}