Thank you for participating!
1971A - My First Sorting Problem
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int x, y;
cin >> x >> y;
cout << min(x, y) << ' ' << max(x, y) << '\n';
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
string s;
cin >> s;
bool ok = false;
for (int i = 1; i < (int)(s.length()); i++) {
if (s[i] != s[0]) {swap(s[i], s[0]); ok = true; break;}
}
if (!ok) {
cout << "NO\n"; return;
}
cout << "YES\n";
cout << s << '\n';
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
string s;
for (int i = 1; i <= 12; i++) {
if (i == a || i == b) {s += "a";}
if (i == c || i == d) {s += "b";}
}
cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n");
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
string s;
cin >> s;
int res = 1;
bool ex = false;
for (int i = 0; i + 1 < (int)(s.size()); i++) {
res += (s[i] != s[i + 1]);
ex |= (s[i] == '0' && s[i + 1] == '1');
}
cout << res - ex << '\n';
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
typedef long long ll;
using namespace std;
void solve()
{
int n, k, q;
cin >> n >> k >> q;
vector<long long> a(k+1), b(k+1);
a[0] = 0;
b[0] = 0;
for(int i = 1; i <= k; i++)
{
cin >> a[i];
}
for(int i = 1; i <= k; i++)
{
cin >> b[i];
}
for(int i = 0; i < q; i++)
{
long long c;
cin >> c;
int l = 0, r = k;
while(l <= r)
{
int mid = l+r>>1;
if(a[mid] > c)
{
r = mid-1;
}
else
{
l = mid+1;
}
}
if(a[r] == c)
{
cout << b[r] << " ";
continue;
}
long long ans = b[r] + (c-a[r])*(b[r+1]-b[r])/(a[r+1]-a[r]);
cout << ans << " ";
}
cout << endl;
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <iostream>
using namespace std;
void solve()
{
long long r;
cin >> r;
long long height = r;
long long ans = 0;
for(long long i = 0; i <= r; i++)
{
while(i*i+height*height >= (r+1)*(r+1))
{
height--;
}
long long cop = height;
while(i*i+cop*cop >= r*r && cop > 0)
{
cop--;
ans++;
}
}
cout << ans*4 << endl;
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
map<int, priority_queue<int>> mp;
for(int i = 0; i < n; i++)
{
cin >> a[i];
mp[a[i]>>2].push(-a[i]);
}
for(int i = 0; i < n; i++)
{
cout << -mp[a[i]>>2].top() << " ";
mp[a[i]>>2].pop();
}
cout << endl;
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
// Reference:
// B. Aspvall, M. Plass, and R. Tarjan,
// A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean
// Formulas
struct two_sat {
public:
two_sat() : _n(0), scc(0) {}
two_sat(int n) : _n(n), _answer(n), scc(2 * n) {}
void add_clause(int i, bool f, int j, bool g) {
assert(0 <= i && i < _n);
assert(0 <= j && j < _n);
scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0));
scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0));
}
bool satisfiable() {
auto id = scc.scc_ids().second;
for (int i = 0; i < _n; i++) {
if (id[2 * i] == id[2 * i + 1]) return false;
_answer[i] = id[2 * i] < id[2 * i + 1];
}
return true;
}
std::vector<bool> answer() { return _answer; }
private:
int _n;
std::vector<bool> _answer;
internal::scc_graph scc;
};
} // namespace atcoder
using namespace std;
using namespace atcoder;
void solve() {
int n;
cin >> n;
int b[3][n];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cin >> b[i][j];
}
}
two_sat ts(n);
for (int j = 0; j < n; j++) {
for (int i = 0; i < 3; i++) {
int nxt = (i + 1) % 3;
ts.add_clause(abs(b[i][j]) - 1, b[i][j] > 0, abs(b[nxt][j]) - 1, b[nxt][j] > 0);
}
}
cout << (ts.satisfiable() ? "YES\n" : "NO\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}