[problem:1690A]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
#define sz(v) (int)v.size()↵
#define all(v) v.begin(),v.end()↵
#define eb emplace_back↵
↵
↵
↵
void solve() {↵
int n; ↵
cin >> n;↵
for (int a = 3; a < n; a++) {↵
int c = (n - a) / 2;↵
int b = n - a - c;↵
if (c > 1 && b+1 < a) {↵
c--;↵
b++;↵
}↵
if (a > b && b > c) {↵
cout << b << ' ' << a << ' ' << c << endl;↵
return;↵
}↵
}↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
↵
forn(tt, t) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690B]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
using namespace std;↵
const int inf = 1e9 + 7;↵
↵
bool equals(vector<int>&a, vector<int>&b, int n){↵
int dif = inf;↵
forn(i, n){↵
if(b[i] != 0) dif = min(dif, a[i] - b[i]);↵
}↵
if(dif < 0) return false; ↵
if(dif == inf) return true;↵
forn(i, n){↵
if(a[i] - b[i] > dif) return false;↵
if(b[i] != 0 && a[i] - b[i] < dif) return false;↵
}↵
return true;↵
}↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<int>a(n), b(n);↵
forn(i, n) cin >> a[i];↵
forn(i, n) cin >> b[i];↵
cout << (equals(a, b, n) ? "YES\n" : "NO\n");↵
↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:1690C]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
↵
void solve() {↵
int n;↵
cin >> n;↵
int s[n];↵
int f[n];↵
for (int i = 0; i < n; ++i) {↵
cin >> s[i];↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
cin >> f[i];↵
}↵
int curTime = 0;↵
int d[n];↵
for (int i = 0; i < n; ++i) {↵
curTime = max(curTime, s[i]);↵
d[i] = f[i] - curTime;↵
curTime = f[i];↵
}↵
for (auto now: d) {↵
cout << now << " ";↵
}↵
cout << '\n';↵
}↵
int main() {↵
int tests;↵
cin >> tests;↵
forn(tt, tests) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690D]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
int main() {↵
int t;↵
cin >> t;↵
forn(tt, t) {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
vector<int> w(n + 1);↵
for (int i = 1; i <= n; i++)↵
w[i] = w[i - 1] + int(s[i - 1] == 'W');↵
int result = INT_MAX;↵
for (int i = k; i <= n; i++)↵
result = min(result, w[i] - w[i - k]);↵
cout << result << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690E]↵
↵
Idea: [user:Vladosiya,2022-06-08], [user:Aris,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define len(s) (int)s.size()↵
using namespace std;↵
using ll = long long;↵
↵
void solve(){↵
int n, k;↵
cin >> n >> k;↵
vector<ll>a(n);↵
ll sum = 0;↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
sum += a[i] / k;↵
a[i] = a[i] % k;↵
}↵
sort(a.begin(), a.end(), [] (int x, int y){↵
return x > y;↵
});↵
↵
for(int i = 0, j = n - 1; i < j; i++, j--){↵
while(a[i] + a[j] < k && i < j) j--;↵
if(i == j) break;↵
sum++;↵
}↵
cout << sum << endl;↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690F]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
def gcd(a, b):↵
if b == 0:↵
return a;↵
return gcd(b, a % b)↵
↵
↵
def shift(s):↵
for i in range(1, len(s) + 1):↵
if s == s[i:] + s[:i]:↵
return i↵
↵
↵
def solve():↵
n = int(input())↵
s = input()↵
p = [int(x)-1 for x in input().split()]↵
used = [False] * n↵
ans = 1↵
i = 0↵
while i < n:↵
ss = ''↵
while not used[i]:↵
ss += s[i]↵
used[i] = True↵
i = p[i];↵
i += 1↵
if len(ss) == 0:↵
continue↵
ln = shift(ss)↵
ans = ans * ln // gcd(ans, ln)↵
print(ans)↵
↵
↵
t = int(input())↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
[problem:1690G]↵
↵
Idea: [user:Aris,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690G]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n);↵
set<int> tmp;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {↵
tmp.insert(i);↵
}↵
}↵
for (int i = 0; i < m; i++) {↵
int j, d;↵
cin >> j >> d;↵
j--;↵
a[j] -= d;↵
auto it = tmp.upper_bound(j);↵
if (it != tmp.begin()) {↵
it = prev(it);↵
if (*it == j || a[*it] > a[j]) {↵
tmp.insert(j);↵
}↵
} else {↵
tmp.insert(j);↵
}↵
while (1) {↵
it = tmp.upper_bound(j);↵
if (it != tmp.end() && a[*it] >= a[j]) {↵
tmp.erase(it);↵
} else {↵
break;↵
}↵
}↵
cout << (int) tmp.size() << " ";↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
#define sz(v) (int)v.size()↵
#define all(v) v.begin(),v.end()↵
#define eb emplace_back↵
↵
↵
↵
void solve() {↵
int n; ↵
cin >> n;↵
for (int a = 3; a < n; a++) {↵
int c = (n - a) / 2;↵
int b = n - a - c;↵
if (c > 1 && b+1 < a) {↵
c--;↵
b++;↵
}↵
if (a > b && b > c) {↵
cout << b << ' ' << a << ' ' << c << endl;↵
return;↵
}↵
}↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
↵
forn(tt, t) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690B]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
using namespace std;↵
const int inf = 1e9 + 7;↵
↵
bool equals(vector<int>&a, vector<int>&b, int n){↵
int dif = inf;↵
forn(i, n){↵
if(b[i] != 0) dif = min(dif, a[i] - b[i]);↵
}↵
if(dif < 0) return false; ↵
if(dif == inf) return true;↵
forn(i, n){↵
if(a[i] - b[i] > dif) return false;↵
if(b[i] != 0 && a[i] - b[i] < dif) return false;↵
}↵
return true;↵
}↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<int>a(n), b(n);↵
forn(i, n) cin >> a[i];↵
forn(i, n) cin >> b[i];↵
cout << (equals(a, b, n) ? "YES\n" : "NO\n");↵
↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:1690C]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
↵
void solve() {↵
int n;↵
cin >> n;↵
int s[n];↵
int f[n];↵
for (int i = 0; i < n; ++i) {↵
cin >> s[i];↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
cin >> f[i];↵
}↵
int curTime = 0;↵
int d[n];↵
for (int i = 0; i < n; ++i) {↵
curTime = max(curTime, s[i]);↵
d[i] = f[i] - curTime;↵
curTime = f[i];↵
}↵
for (auto now: d) {↵
cout << now << " ";↵
}↵
cout << '\n';↵
}↵
int main() {↵
int tests;↵
cin >> tests;↵
forn(tt, tests) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690D]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
↵
int main() {↵
int t;↵
cin >> t;↵
forn(tt, t) {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
vector<int> w(n + 1);↵
for (int i = 1; i <= n; i++)↵
w[i] = w[i - 1] + int(s[i - 1] == 'W');↵
int result = INT_MAX;↵
for (int i = k; i <= n; i++)↵
result = min(result, w[i] - w[i - k]);↵
cout << result << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690E]↵
↵
Idea: [user:Vladosiya,2022-06-08], [user:Aris,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define len(s) (int)s.size()↵
using namespace std;↵
using ll = long long;↵
↵
void solve(){↵
int n, k;↵
cin >> n >> k;↵
vector<ll>a(n);↵
ll sum = 0;↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
sum += a[i] / k;↵
a[i] = a[i] % k;↵
}↵
sort(a.begin(), a.end(), [] (int x, int y){↵
return x > y;↵
});↵
↵
for(int i = 0, j = n - 1; i < j; i++, j--){↵
while(a[i] + a[j] < k && i < j) j--;↵
if(i == j) break;↵
sum++;↵
}↵
cout << sum << endl;↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1690F]↵
↵
Idea: [user:MikeMirzayanov,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
def gcd(a, b):↵
if b == 0:↵
return a;↵
return gcd(b, a % b)↵
↵
↵
def shift(s):↵
for i in range(1, len(s) + 1):↵
if s == s[i:] + s[:i]:↵
return i↵
↵
↵
def solve():↵
n = int(input())↵
s = input()↵
p = [int(x)-1 for x in input().split()]↵
used = [False] * n↵
ans = 1↵
i = 0↵
while i < n:↵
ss = ''↵
while not used[i]:↵
ss += s[i]↵
used[i] = True↵
i = p[i];↵
i += 1↵
if len(ss) == 0:↵
continue↵
ln = shift(ss)↵
ans = ans * ln // gcd(ans, ln)↵
print(ans)↵
↵
↵
t = int(input())↵
for _ in range(t):↵
solve()↵
~~~~~↵
</spoiler>↵
↵
[problem:1690G]↵
↵
Idea: [user:Aris,2022-06-08]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1690G]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n);↵
set<int> tmp;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {↵
tmp.insert(i);↵
}↵
}↵
for (int i = 0; i < m; i++) {↵
int j, d;↵
cin >> j >> d;↵
j--;↵
a[j] -= d;↵
auto it = tmp.upper_bound(j);↵
if (it != tmp.begin()) {↵
it = prev(it);↵
if (*it == j || a[*it] > a[j]) {↵
tmp.insert(j);↵
}↵
} else {↵
tmp.insert(j);↵
}↵
while (1) {↵
it = tmp.upper_bound(j);↵
if (it != tmp.end() && a[*it] >= a[j]) {↵
tmp.erase(it);↵
} else {↵
break;↵
}↵
}↵
cout << (int) tmp.size() << " ";↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
