Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def solve():
n = int(input())
s1 = input()
s2 = input()
bad = False
for i in range(n):
bad |= s1[i] == '1' and s2[i] == '1'
if bad:
print('NO')
else:
print('YES')
t = int(input())
for i in range(t):
solve()
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
a = [[] for i in range(n)]
for j in range(n):
a[j] = list(map(int, input().split()))
ans = False
for j in range(5):
for k in range(5):
if k != j:
cnt1 = 0
cnt2 = 0
cntno = 0
for z in range(n):
if a[z][j] == 1:
cnt1 += 1
if a[z][k] == 1:
cnt2 += 1
if a[z][j] == 0 and a[z][k] == 0:
cntno += 1
if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:
ans = True
if ans:
print('YES')
else:
print('NO')
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<int> a(n);
map<int, int> cnt;
for (auto &x : a) {
scanf("%d", &x);
cnt[x] += 1;
}
long long sum = accumulate(a.begin(), a.end(), 0LL);
if ((2 * sum) % n != 0) {
puts("0");
continue;
}
long long need = (2 * sum) / n;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int a1 = a[i];
int a2 = need - a1;
if (cnt.count(a2)) ans += cnt[a2];
if (a1 == a2) ans -= 1;
}
printf("%lld\n", ans / 2);
}
}
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;
cin >> n;
vector<int> a(n), b(n), ca(n + 1), cb(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
ca[a[i]]++; cb[b[i]]++;
}
long long ans = n * 1LL * (n - 1) * (n - 2) / 6;
for (int i = 0; i < n; ++i)
ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1);
cout << ans << '\n';
}
}
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;
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
vector<vector<int>> a(n, vector<int>(m, 1));
long long ans = 0;
forn(x, n) forn(y, m){
if (x == 0){
for (int k = 1;; ++k){
int nx = x + k / 2;
int ny = y + (k + 1) / 2;
if (nx == n || ny == m) break;
ans += k;
}
}
if (y == 0){
for (int k = 1;; ++k){
int nx = x + (k + 1) / 2;
int ny = y + k / 2;
if (nx == n || ny == m) break;
ans += k;
}
}
}
ans += n * m;
forn(i, q){
int x, y;
scanf("%d%d", &x, &y);
--x, --y;
forn(c, 2){
int l = 1, r = 1;
while (true){
int nx = x + (l + c) / 2;
int ny = y + (l + !c) / 2;
if (nx == n || ny == m || a[nx][ny] == 0) break;
++l;
}
while (true){
int nx = x - (r + !c) / 2;
int ny = y - (r + c) / 2;
if (nx < 0 || ny < 0 || a[nx][ny] == 0) break;
++r;
}
if (a[x][y] == 0){
ans += l * r;
}
else{
ans -= l * r;
}
}
ans += a[x][y];
a[x][y] ^= 1;
ans -= a[x][y];
printf("%lld\n", ans);
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const int N = 20;
const int M = (1 << N);
struct BracketSeqn
{
int balance;
int lowestBalance;
vector<int> queryAns;
pair<int, bool> go(int x, bool f)
{
if(f)
return make_pair(0, true);
else
return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0);
}
BracketSeqn() {};
BracketSeqn(string s)
{
vector<int> bal;
int cur = 0;
int n = s.size();
for(auto x : s)
{
if(x == '(')
cur++;
else
cur--;
bal.push_back(cur);
}
balance = bal.back();
lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
vector<vector<int>> negPos(-lowestBalance + 1);
for(int i = 0; i < n; i++)
{
if(bal[i] > 0) continue;
negPos[-bal[i]].push_back(i);
}
queryAns.resize(-lowestBalance + 1);
for(int i = 0; i < queryAns.size(); i++)
{
int lastPos = int(1e9);
if(i != -lowestBalance)
lastPos = negPos[i + 1][0];
queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin();
}
};
};
int dp[M][2];
char buf[M];
int total_bal[M];
int main()
{
int n;
scanf("%d", &n);
vector<BracketSeqn> bs;
for(int i = 0; i < n; i++)
{
scanf("%s", buf);
string s = buf;
bs.push_back(BracketSeqn(s));
}
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
if(i & (1 << j))
total_bal[i] += bs[j].balance;
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < 2; j++)
dp[i][j] = -int(1e9);
dp[0][0] = 0;
for(int i = 0; i < (1 << n); i++)
for(int f = 0; f < 2; f++)
{
if(dp[i][f] < 0) continue;
for(int k = 0; k < n; k++)
{
if(i & (1 << k)) continue;
pair<int, bool> res = bs[k].go(total_bal[i], f);
dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
}
}
printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
}
1598G - The Sum of Good Numbers
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD[] = { 597804841, 618557587, 998244353 };
const int N = 500 * 1000 + 13;
const int K = 3;
using hs = array<int, K>;
int add(int x, int y, int mod) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
return x;
}
int mul(int x, int y, int mod) {
return x * 1LL * y % mod;
}
hs get(const int& x) {
hs c;
forn(i, K) c[i] = x;
return c;
}
hs operator +(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = add(a[i], b[i], MOD[i]);
return c;
}
hs operator -(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = add(a[i], -b[i], MOD[i]);
return c;
}
hs operator *(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = mul(a[i], b[i], MOD[i]);
return c;
}
int n, m;
string s, sx;
hs sum[N], pw[N];
hs get(int l, int r) {
return sum[r] - sum[l] * pw[r - l];
}
vector<int> zfunction(const string& s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r) z[i] = min(z[i - l], r - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s >> sx;
n = s.size();
m = sx.size();
pw[0] = get(1);
forn(i, N - 1) pw[i + 1] = pw[i] * get(10);
sum[0] = get(0);
forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0');
hs x = get(0);
forn(i, m) x = x * get(10) + get(sx[i] - '0');
if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) {
if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) {
cout << i + 1 << ' ' << i + m - 1 << '\n';
cout << i + m << ' ' << i + 2 * (m - 1) << '\n';
return 0;
}
}
auto z = zfunction(sx + "#" + s);
for (int i = 0; i + m <= n; ++i) {
int lcp = z[m + i + 1];
for (int len = m - lcp - 1; len <= m - lcp; ++len) {
if (len < 1) continue;
if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) {
cout << i + 1 << ' ' << i + m << '\n';
cout << i + m + 1 << ' ' << i + m + len << '\n';
return 0;
}
if (i >= len && get(i - len, i) + get(i, i + m) == x) {
cout << i - len + 1 << ' ' << i << '\n';
cout << i + 1 << ' ' << i + m << '\n';
return 0;
}
}
}
assert(false);
}