Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
bool solve() {
string s;
cin >> s;
vector<int> d(3);
int x = s[0] - 'A';
int y = s.back() - 'A';
if (x == y)
return false;
d[x] = 1; d[y] = -1;
if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
d[3 ^ x ^ y] = -1;
else
d[3 ^ x ^ y] = 1;
int bal = 0;
for (char c : s) {
bal += d[c - 'A'];
if (bal < 0) return false;
}
return bal == 0;
}
int main() {
int t; cin >> t;
while (t--) {
cout << (solve() ? "YES\n" : "NO\n");
}
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n, U, R, D, L = map(int, input().split())
for mask in range(16):
rU, rR, rD, rL = U, R, D, L
if mask & 1:
rU -= 1
rL -= 1
if mask & 2:
rL -= 1
rD -= 1
if mask & 4:
rD -= 1
rR -= 1
if mask & 8:
rR -= 1
rU -= 1
if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
print("YES")
break
else:
print("NO")
Idea: adedalic
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 calc(const vector<int> &a, const vector<int> &b){
int n = a.size();
int m = b.size();
vector<int> su(n + 1);
int r = m - 1;
for (int i = n - 1; i >= 0; --i){
su[i] = su[i + 1];
while (r >= 0 && b[r] > a[i]) --r;
if (r >= 0 && b[r] == a[i]) ++su[i];
}
int ans = 0;
int j = 0;
r = 0;
forn(l, m){
while (j < n && a[j] <= b[l] + j) ++j;
while (r < m && b[r] - b[l] < j) ++r;
ans = max(ans, r - l + su[j]);
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n), b(m);
forn(i, n) scanf("%d", &a[i]);
forn(i, m) scanf("%d", &b[i]);
vector<int> al, bl, ar, br;
forn(i, n){
if (a[i] < 0) al.push_back(-a[i]);
else ar.push_back(a[i]);
}
forn(i, m){
if (b[i] < 0) bl.push_back(-b[i]);
else br.push_back(b[i]);
}
reverse(al.begin(), al.end());
reverse(bl.begin(), bl.end());
printf("%d\n", calc(al, bl) + calc(ar, br));
}
return 0;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
const int N = 505;
int n;
int a[N][N];
int c[2 * N];
vector<pair<int, int>> e;
int calc(vector<int> ls) {
if (sz(ls) == 1)
return ls[0];
int res = -1;
for (int u : ls)
res = max(res, a[ls[0]][u]);
vector<vector<int>> ch;
ch.push_back({ls[0]});
for (int i = 1; i < sz(ls); ++i) {
int v = ls[i];
int group = -1;
for (int j = 0; j < sz(ch); ++j) {
if (a[v][ch[j][0]] != res) {
group = j;
break;
}
}
if (group == -1) {
group = sz(ch);
ch.push_back({});
}
ch[group].push_back(v);
}
int v = n++;
c[v] = res;
for (int i = 0; i < sz(ch); ++i) {
int u = calc(ch[i]);
e.emplace_back(u, v);
}
return v;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];
for (int i = 0; i < n; ++i)
c[i] = a[i][i];
vector<int> ls(n);
iota(ls.begin(), ls.end(), 0);
int root = calc(ls);
cout << n << '\n';
for (int i = 0; i < n; ++i)
cout << c[i] << ' ';
cout << '\n' << root + 1 << '\n';
for (auto it : e)
cout << it.first + 1 << ' ' << it.second + 1 << '\n';
}
Idea: adedalic
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 x first
#define y second
typedef pair<int, int> pt;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
map<pt, int> allEdges;
set<pt> difPairs, eqPairs;
fore (q, 0, m) {
char tp; cin >> tp;
if (tp == '+') {
int u, v;
char c;
cin >> u >> v >> c;
if (allEdges.count({v, u})) {
if (allEdges[{v, u}] == c)
eqPairs.emplace(min(u, v), max(u, v));
else
difPairs.emplace(min(u, v), max(u, v));
}
allEdges[{u, v}] = c;
} else if (tp == '-') {
int u, v;
cin >> u >> v;
if (eqPairs.count({min(u, v), max(u, v)}))
eqPairs.erase({min(u, v), max(u, v)});
if (difPairs.count({min(u, v), max(u, v)}))
difPairs.erase({min(u, v), max(u, v)});
allEdges.erase({u, v});
} else {
int k;
cin >> k;
bool hasAns = !eqPairs.empty();
if (k & 1)
hasAns |= !difPairs.empty();
cout << (hasAns ? "YES" : "NO") << '\n';
}
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 300043;
int n, m;
set<int> g[N];
set<int> g2[N];
vector<int> res;
void euler(int x)
{
while(!g2[x].empty())
{
int y = *g2[x].begin();
g2[x].erase(y);
g2[y].erase(x);
euler(y);
}
res.push_back(x);
}
bool check(int c)
{
for(int i = 1; i <= n; i++)
g2[i] = g[i];
res = vector<int>();
euler(c);
int curm = 0;
for(int i = 1; i <= n; i++)
curm += g[i].size();
for(int i = 1; i <= n; i++)
g2[i] = g[i];
for(int i = 1; i < res.size(); i++)
{
int x = res[i - 1];
int y = res[i];
if(g2[x].count(y) != 1)
return false;
g2[x].erase(y);
g2[y].erase(x);
}
return curm / 2 + 1 == res.size();
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
g[x].insert(y);
g[y].insert(x);
}
for(int i = 1; i <= n; i++)
{
set<int> pr = g[i];
set<int> diff;
for(auto x : pr)
if(g[x].size() % 2 == 1)
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
if(check(i))
{
res.push_back(-1);
for(auto x : diff)
{
res.push_back(x);
res.push_back(i);
}
printf("%d\n", res.size());
for(auto x : res) printf("%d ", x);
puts("");
exit(0);
}
for(auto x : pr)
{
if(g[i].count(x))
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
else
{
g[i].insert(x);
g[x].insert(i);
diff.erase(x);
}
if(check(i))
{
res.push_back(-1);
for(auto x : diff)
{
res.push_back(x);
res.push_back(i);
}
printf("%d\n", res.size());
for(auto x : res) printf("%d ", x);
puts("");
exit(0);
}
if(g[i].count(x))
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
else
{
g[i].insert(x);
g[x].insert(i);
diff.erase(x);
}
}
for(auto x : diff)
{
g[i].insert(x);
g[x].insert(i);
}
}
puts("0");
}