Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <cmath>
- #include <map>
- #include <utility>
- #include <fstream>
- #include <bitset>
- #include <deque>
- typedef long long int ll;
- #define all(x) (x).begin(),(x).end()
- #define endl "\n";
- long double pi = 3.14159265358979;
- using namespace std;
- int inf = 1e12;
- ll MOD = 998244353;
- void fastIO() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- }
- vector <vector <int>> gr;
- vector <int> dist(int v, int n) {
- vector <int> d(n, -1);
- d[v] = 0;
- deque<int> q;
- q.push_back(v);
- while (!q.empty()) {
- int u = q.front();
- q.pop_front();
- for (int l : gr[u])
- if (d[l] == -1) {
- d[l] = d[u] + 1;
- q.push_back(l);
- }
- }
- return d;
- }
- int lmao(vector <int>& a, int d) {
- for (int i = 0; i < a.size(); i++)
- if (a[i] == d)
- return i;
- }
- void solve() {
- int n;
- cin >> n;
- vector <int> a(n);
- for (int i = 0; i < n; i++) cin >> a[i];
- int ind = n - 1;
- int d = 1;
- int l = n;
- while (ind > 0) {
- while (a[ind] != d) ind--;
- for (int i = ind + 1; i < l; i++)
- if (a[i] == a[i - 1] + 1)
- d++;
- else {
- cout << "No\n";
- return;
- }
- l = ind;
- d++;
- }
- cout << "Yes\n";
- return;
- }
- int main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) solve();
- }
- //*****************************************************************************************
- //task 2.3
- void solve(int n) {
- cout << n << " " << n - 1 << " " << n - 2;
- }
- //task 2.4
- int getp(vector <int>& parent, int v) {
- if (parent[v] == v)
- return v;
- else {
- int u = getp(parent, parent[v]);
- parent[v] = u;
- return parent[v];
- }
- }
- void Union(vector <int>& parent, int v, int u) {
- v = getp(parent, v);
- u = getp(parent, u);
- if (v != u)
- parent[v] = u;
- }
- void solve(int n, int m, int q) {
- vector <vector <int>> a(n, vector <int>(m, 0));
- vector <int> parent(n * m);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- parent[j + i * m] = j + i * m;
- int res = 0;
- set <int> s;
- for (int l = 0; l < q; l++) {
- int i, j;
- cin >> i >> j;
- if (a[i][j] == 1) continue;
- if (a[i - 1][j] == 1) s.insert(parent[j + (i - 1) * m]);
- if (a[i + 1][j] == 1) s.insert(parent[j + (i + 1) * m]);
- if (a[i][j - 1] == 1) s.insert(parent[j - 1 + i * m]);
- if (a[i][j + 1] == 1) s.insert(parent[j + 1 + i * m]);
- if (s.size() == 0) res++;
- else if (s.size() == 2) {
- res--;
- int k = *s.begin();
- s.erase(k);
- Union(parent, k, *s.begin());
- }
- else if (s.size() == 3) {
- int k = *s.begin();
- s.erase(k);
- int d = *s.begin();
- s.erase(d);
- Union(parent, k, d);
- Union(parent, k, *s.begin());
- }
- else if (s.size() == 4) {
- int k = *s.begin();
- s.erase(k);
- int d = *s.begin();
- s.erase(d);
- int p = *s.begin();
- s.erase(p);
- Union(parent, k, d);
- Union(parent, k, p);
- Union(parent, k, *s.begin());
- }
- s.clear();
- }
- }
- //task 2.1
- void solve(vector <vector <pair<int, int>>> gr, int s, int t) {
- vector <int> d(gr.size(), 1e9);
- d[s] = 0;
- deque<int> q;
- q.push_back(s);
- while (!q.empty()) {
- int v = q.front();
- q.pop_front();
- for (pair <int, int> u : gr[v])
- if (d[u.first] > d[v] + u.second) {
- d[u.first] = d[v] + u.second;
- if (u.second == 0)
- q.push_front(u.first);
- else q.push_back(u.first);
- }
- }
- cout << d[t];
- }
- //task 2.2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement