1102A - Integer Sequence Dividing
Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
n %= 4;
if (n == 0 || n == 3) {
cout << 0 << endl;
} else {
cout << 1 << endl;
}
return 0;
}
Solution 2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
long long sum = n * 1ll * (n + 1) / 2;
cout << (sum & 1) << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
sort(a.begin(), a.end());
vector<vector<int>> buckets(k);
vector<int> res(n);
for (int i = 0; i < n; ++i) {
buckets[i % k].push_back(a[i].first);
res[a[i].second] = i % k;
}
for (int i = 0; i < k; ++i) {
for (int j = 0; j < int(buckets[i].size()) - 1; ++j) {
if (buckets[i][j] == buckets[i][j + 1]) {
cout << "NO" << endl;
return 0;
}
}
}
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cout << res[i] + 1 << " ";
}
cout << endl;
return 0;
}
1102C - Doors Breaking and Repairing
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, x, y;
cin >> n >> x >> y;
int cnt = 0;
for (int i = 0; i < n; ++i) {
int cur;
cin >> cur;
if (cur <= x) {
++cnt;
}
}
if (x > y) {
cout << n << endl;
} else {
cout << (cnt + 1) / 2 << endl;
}
return 0;
}
1102D - Balanced Ternary String
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int n;
int needRep(const vector<int> &cnt, const vector<int> &need) {
int res = 0;
for (int i = 0; i < 3; ++i) {
res += abs(cnt[i] - need[i]);
}
assert(res % 2 == 0);
return res / 2;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
string s;
cin >> n >> s;
vector<int> cnt(3), cur(3, n / 3);
for (auto c : s) {
++cnt[c - '0'];
}
int need = needRep(cnt, cur);
int curRep = 0;
for (int i = 0; i < n; ++i) {
--cnt[s[i] - '0'];
for (int j = 0; j < 3; ++j) {
if (cur[j] == 0) continue;
int rep = j != s[i] - '0';
--cur[j];
if (curRep + rep + needRep(cnt, cur) == need) {
s[i] = j + '0';
curRep += rep;
break;
}
++cur[j];
}
}
cout << s << endl;
return 0;
}
Solution (PikMike)
n = int(input())
s = [ord(x) - ord('0') for x in input()]
cnt = [s.count(x) for x in [0, 1, 2]]
def forw(x):
for i in range(n):
if (cnt[x] < n // 3 and s[i] > x and cnt[s[i]] > n // 3):
cnt[x] += 1
cnt[s[i]] -= 1
s[i] = x
def back(x):
for i in range(n - 1, -1, -1):
if (cnt[x] < n // 3 and s[i] < x and cnt[s[i]] > n // 3):
cnt[x] += 1
cnt[s[i]] -= 1
s[i] = x
forw(0)
forw(1)
back(2)
back(1)
print(''.join([str(x) for x in s]))
1102E - Monotonic Renumeration
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
map<int, int> lst;
vector<int> last_pos(n);
for(int i = n - 1; i >= 0; i--)
{
if(!lst.count(a[i]))
lst[a[i]] = i;
last_pos[i] = lst[a[i]];
}
int ans = 1;
int cur_max = -1;
for(int i = 0; i < n - 1; i++)
{
cur_max = max(cur_max, last_pos[i]);
if(cur_max == i)
ans = (2 * ans) % MOD;
}
printf("%d\n", ans);
return 0;
}
Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long li;
const int N = 18;
const int M = 100 * 1000 + 13;
const int INF = 1e9;
int dp[1 << N][N];
int n, m;
int a[N][M];
int mn1[N][N], mn2[N][N];
int calc(int mask, int v){
if (dp[mask][v] != -1)
return dp[mask][v];
dp[mask][v] = 0;
forn(u, n) if (v != u && ((mask >> u) & 1))
dp[mask][v] = max(dp[mask][v], min(mn1[u][v], calc(mask ^ (1 << v), u)));
return dp[mask][v];
}
int main() {
scanf("%d%d", &n, &m);
forn(i, n) forn(j, m)
scanf("%d", &a[i][j]);
forn(i, n) forn(j, n){
int val = INF;
forn(k, m)
val = min(val, abs(a[i][k] - a[j][k]));
mn1[i][j] = val;
val = INF;
forn(k, m - 1)
val = min(val, abs(a[i][k] - a[j][k + 1]));
mn2[i][j] = val;
}
int ans = 0;
forn(i, n){
memset(dp, -1, sizeof(dp));
forn(j, n)
dp[1 << j][j] = (j == i ? INF : 0);
forn(j, n)
ans = max(ans, min(mn2[j][i], calc((1 << n) - 1, j)));
}
printf("%d\n", ans);
}
Solution 2
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 18;
const int M = 100 * 1000 + 13;
const int INF = 1e9;
int used[1 << N];
char dp[1 << N];
int g[1 << N];
int n, m;
int a[N][M];
int mn1[N][N], mn2[N][N];
bool calc(int mask){
if (dp[mask] != -1)
return dp[mask];
used[mask] = 0;
dp[mask] = 0;
forn(i, n){
if (!((mask >> i) & 1))
continue;
if (!calc(mask ^ (1 << i)))
continue;
if (!(used[mask ^ (1 << i)] & g[i]))
continue;
used[mask] |= (1 << i);
dp[mask] = 1;
}
return dp[mask];
}
bool check(int k){
forn(i, n){
g[i] = 0;
forn(j, n)
g[i] |= (1 << j) * (mn1[j][i] >= k);
}
forn(i, n){
memset(dp, -1, sizeof(dp));
forn(j, n){
dp[1 << j] = (j == i);
used[1 << j] = (1 << j);
}
calc((1 << n) - 1);
forn(j, n) if (mn2[j][i] >= k && ((used[(1 << n) - 1] >> j) & 1))
return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
forn(i, n) forn(j, m)
scanf("%d", &a[i][j]);
forn(i, n) forn(j, n){
int val = INF;
forn(k, m)
val = min(val, abs(a[i][k] - a[j][k]));
mn1[i][j] = val;
val = INF;
forn(k, m - 1)
val = min(val, abs(a[i][k] - a[j][k + 1]));
mn2[i][j] = val;
}
int l = 0, r = INF;
while (l < r - 1){
int m = (l + r) / 2;
if (check(m))
l = m;
else
r = m;
}
printf("%d\n", check(r) ? r : l);
}