Here are the editorials for all the problems. Hope you enjoyed them and found them interesting!
The tutorial currently shows that it is unavailable for now. It will appear after system tests.
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int N = 1000;
char bus[N][5];
void printbus(int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 5; j++)
{
cout << bus[i][j];
}
cout << '\n';
}
}
void yes()
{
cout << "YES" << '\n';
}
void no()
{
cout << "NO" << '\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 5; j++)
{
cin >> bus[i][j];
}
}
bool possible = false;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 2; j++)
{
if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O')
{
bus[i][j*3] = '+';
bus[i][j*3+1] = '+';
possible = true;
break;
}
}
if(possible) break;
}
if(!possible)
{
no();
return 0;
}
else
{
yes();
printbus(n);
return 0;
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LG = 20;
ll a[1001][1001];
ll r[1001]; //row sum
ll c[1001]; //column sum
int n;
void no()
{
cout << -1 << '\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
int x, y; ll diagonal1 = 0; ll diagonal2 = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
if(a[i][j] == 0)
{
x = i; y = j;
}
else
{
r[i] += a[i][j];
c[j] += a[i][j];
if(i == j)
{
diagonal1 += a[i][j];
}
if(i + j == n - 1)
{
diagonal2 += a[i][j];
}
}
}
}
if(n == 1)
{
cout << 1 << '\n';
return 0;
}
ll commonsum = r[0];
if(x == 0) commonsum = r[1];
//cout << commonsum << '\n';
ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1;
for(int i = 0; i < n; i++)
{
if(i != x)
{
if(r[i] != commonsum)
{
no();
return 0;
}
}
else
{
rowsum = r[i];
}
}
for(int i = 0; i < n; i++)
{
if(i != y)
{
if(c[i] != commonsum)
{
no(); return 0;
}
}
else
{
colsum = c[i];
}
}
bool isdiagonal1 = false; bool isdiagonal2 = false;
if(x == y) isdiagonal1 = true;
if(x + y == n - 1) isdiagonal2 = true;
if(!isdiagonal1)
{
if(diagonal1 != commonsum)
{
no();
return 0;
}
}
else
{
d1sum = diagonal1;
}
if(!isdiagonal2)
{
if(diagonal2 != commonsum)
{
no();
return 0;
}
}
else
{
d2sum = diagonal2;
}
if(rowsum == colsum)
{
if(isdiagonal1 && d1sum != rowsum)
{
no();
return 0;
}
if(isdiagonal2 && d2sum != rowsum)
{
no();
return 0;
}
ll value = commonsum - rowsum;
if(value > 0)
{
cout << value << '\n';
return 0;
}
else
{
no();
return 0;
}
}
else
{
no();
return 0;
}
}
Tutorial is loading...
Code (O(nkm^2))
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int N = 101;
const int MOD = 1e9 + 7;
const ll INF = ll(1e18);
ll dp[N][N][N];
int c[N];
ll cost[N][N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
{
cin >> c[i];
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= k; j++)
{
for(int a = 0; a <= m; a++)
{
dp[i][j][a] = INF;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> cost[i][j];
}
}
if(c[1] == 0)
{
for(int i = 1; i <= m; i++)
{
dp[1][1][i] = cost[1][i];
}
}
else
{
dp[1][1][c[1]] = 0;
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
if(c[i] == 0)
{
for(int a = 1; a <= m; a++)
{
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
for(int b = 1; b <= m; b++)
{
if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]);
}
}
}
else
{
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
for(int b = 1; b <= m; b++)
{
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
}
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
}
}
}
ll ans = INF;
for(int i = 1; i <= m; i++)
{
ans = min(ans, dp[n][k][i]);
}
if(ans >= INF) ans = -1;
cout << ans;
}
Code (O(nkm))
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int N = 101;
const int MOD = 1e9 + 7;
const ll INF = ll(1e18);
ll dp[N][N][N];
int c[N];
ll cost[N][N];
ll idx[N][N];
ll m1[N][N];
ll m2[N][N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
{
cin >> c[i];
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= k; j++)
{
m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1;
for(int a = 0; a <= m; a++)
{
dp[i][j][a] = INF;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> cost[i][j];
}
}
if(c[1] == 0)
{
for(int i = 1; i <= m; i++)
{
dp[1][1][i] = cost[1][i];
if(dp[1][1][i] <= m1[1][1])
{
if(dp[1][1][i] == m1[1][1])
{
idx[1][1] = -2;
}
else
{
idx[1][1] = i;
}
m2[1][1] = m1[1][1];
m1[1][1] = dp[1][1][i];
}
else if(dp[1][1][i] <= m2[1][1])
{
m2[1][1] = dp[1][1][i];
}
}
}
else
{
dp[1][1][c[1]] = 0;
m1[1][1] = 0; idx[1][1] = c[1];
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
if(c[i] == 0)
{
for(int a = 1; a <= m; a++)
{
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
ll tmp = INF;
if(a == idx[i-1][j-1])
{
tmp = m2[i-1][j-1];
}
else
{
tmp = m1[i-1][j-1];
}
dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]);
}
}
else
{
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
for(int b = 1; b <= m; b++)
{
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
}
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
}
for(int a = 1; a <= m; a++)
{
if(dp[i][j][a] <= m1[i][j])
{
if(dp[i][j][a] == m1[i][j])
{
idx[i][j] = -2;
}
else
{
idx[i][j] = a;
}
m2[i][j] = m1[i][j];
m1[i][j] = dp[i][j][a];
}
else if(dp[i][j][a] <= m2[i][j])
{
m2[i][j] = dp[i][j][a];
}
}
}
}
ll ans = INF;
for(int i = 1; i <= m; i++)
{
ans = min(ans, dp[n][k][i]);
}
if(ans >= INF) ans = -1;
cout << ans;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int N = 1e6 + 3;
int a[N];
int visited[N];
ll ans;
vector<int> cycles;
ll dp[N];
int cyclecnt;
void dfs2(int u)
{
cycles[cyclecnt]++;
visited[u] = 3;
if(visited[a[u]] == 3) return ;
dfs2(a[u]);
}
void dfs(int u)
{
visited[u] = 2;
if(visited[a[u]] == 0)
{
dfs(a[u]);
}
else if(visited[a[u]] == 1)
{
visited[u] = 1;
return ;
}
else
{
cycles.pb(0);
dfs2(u);
cyclecnt++;
}
visited[u] = 1;
}
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
dp[i] = (dp[i-1]*2LL)%MOD;
}
ans = 1;
memset(visited, 0, sizeof(visited));
for(int i = 1; i <= n; i++)
{
if(visited[i] == 0)
{
dfs(i);
}
}
ll cnt = n;
for(int i = 0; i < cycles.size(); i++)
{
cnt -= cycles[i];
ans = (ans*(dp[cycles[i]]-2+MOD))%MOD;
}
ans = (ans*dp[cnt])%MOD;
if(ans < 0) ans += MOD;
int ans2 = ans;
printf("%d\n", ans2);
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MOD = 1e6 + 3;
ll power(ll base, ll exp)
{
ll ans = 1;
while(exp)
{
if(exp&1) ans = (ans*base)%MOD;
base = (base*base)%MOD;
exp>>=1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
ll n, k;
cin >> n >> k;
if(n <= 63 && k > (1LL<<n))
{
cout << 1 << " " << 1;
return 0;
}
ll v2 = 0;
int digits = __builtin_popcountll(k - 1);
v2 = k - 1 - digits;
ll ntmp = n % (MOD - 1);
if(ntmp < 0) ntmp += (MOD - 1);
ll ktmp = k % (MOD - 1);
if(ktmp < 0) ktmp += (MOD - 1);
ll v2tmp = v2 % (MOD - 1);
if(v2tmp < 0) v2tmp += (MOD - 1);
ll exponent = ntmp*(ktmp - 1) - v2tmp;
exponent %= (MOD - 1);
if(exponent < 0) exponent += MOD - 1;
ll denom = power(2, exponent);
ll numpart = 0;
if(k - 1 >= MOD)
{
numpart = 0;
}
else
{
ll prod = 1;
ll ntmp2 = power(2, ntmp);
prod = power(2, v2tmp);
prod = power(prod, MOD - 2);
if(prod < 0) prod += MOD;
for(ll y = 1; y <= k - 1; y++)
{
prod = (prod * (ntmp2 - y))%MOD;
}
numpart = prod;
}
ll num = (denom - numpart)%MOD;
num %= MOD; denom %= MOD;
if(num < 0) num += MOD;
if(denom < 0) denom += MOD;
cout << num << " " << denom;
return 0;
}
