Tutorial
Tutorial is loading...
Solution (Roms)
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
int tc;
cin >> tc;
for(int t = 0; t < tc; ++t){
cin >> n >> s;
int pos = n;
for(int i = 0; i < n; ++i)
if(s[i] == '8'){
pos = i;
break;
}
if(n - pos >= 11)
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
vector<int> p = {4, 8, 15, 16, 23, 42};
int ans[4];
int main()
{
for(int i = 0; i < 4; i++)
{
cout << "? " << i + 1 << " " << i + 2 << endl;
cout.flush();
cin >> ans[i];
}
do
{
bool good = true;
for(int i = 0; i < 4; i++)
good &= (p[i] * p[i + 1] == ans[i]);
if(good) break;
}
while(next_permutation(p.begin(), p.end()));
cout << "!";
for(int i = 0; i < 6; i++)
cout << " " << p[i];
cout << endl;
cout.flush();
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000043;
vector<int> g[N];
int color[N];
int siz[N];
int n, m;
int cc = 0;
int dfs(int x)
{
if(color[x])
return 0;
color[x] = cc;
int ans = (x < n ? 1 : 0);
for(auto y : g[x])
ans += dfs(y);
return ans;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int k;
scanf("%d", &k);
for(int j = 0; j < k; j++)
{
int x;
scanf("%d", &x);
--x;
g[x].push_back(i + n);
g[i + n].push_back(x);
}
}
for(int i = 0; i < n; i++)
{
if(!color[i])
{
cc++;
siz[cc] = dfs(i);
}
printf("%d ", siz[color[i]]);
}
}
Solution (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 500 * 1000 + 13;
int n, m;
int rk[N], p[N];
int getP(int a){
return (a == p[a] ? a : p[a] = getP(p[a]));
}
void unite(int a, int b){
a = getP(a), b = getP(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
p[b] = a;
rk[a] += rk[b];
}
int main(){
scanf("%d%d", &n, &m);
forn(i, n) p[i] = i, rk[i] = 1;
forn(i, m){
int k;
scanf("%d", &k);
int lst = -1;
forn(j, k){
int x;
scanf("%d", &x);
--x;
if (lst != -1)
unite(x, lst);
lst = x;
}
}
forn(i, n)
printf("%d ", rk[getP(i)]);
puts("");
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
int n;
string s;
inline bool read() {
if(!(cin >> n))
return false;
cin >> s;
return true;
}
inline void solve() {
string t(n, '0');
int bal = 0;
fore(i, 0, n) {
if(s[i] == ')')
bal--;
t[i] = char('0' + (bal & 1));
if(s[i] == '(')
bal++;
}
cout << t << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 99;
int n, x;
int a[N];
vector <int> pos[N];
int prefMax[N];
int main() {
scanf("%d %d", &n, &x);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
pos[a[i]].push_back(i);
prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i]));
}
int p = 1;
int lst = n + 5;
for(int i = x; i >= 1; --i){
if(pos[i].empty()){
p = i;
continue;
}
if(pos[i].back() > lst) break;
p = i;
lst = pos[i][0];
}
long long res = 0;
lst = -1;
for(int l = 1; l <= x; ++l){
int r = max(l, p - 1);
if(lst != -1) r = max(r, prefMax[lst]);
res += x - r + 1;
if(!pos[l].empty()){
if(pos[l][0] < lst) break;
lst = pos[l].back();
}
}
cout << res << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
const int MOD = int(1e9) + 7;
int add(int a, int b) {
a += b;
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
vector<li> f;
void inc(int pos, int val) {
for(; pos < sz(f); pos |= pos + 1)
f[pos] += val;
}
li sum(int pos) {
li ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += f[pos];
return ans;
}
vector<int> S[2];
inline void solve() {
fore(k, 0, 2) {
S[k].assign(n, 0);
f.assign(n, 0);
vector<int> dx(a.begin(), a.end());
sort(dx.begin(), dx.end());
fore(i, 0, n) {
int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin());
S[k][i] = int(sum(pos) % MOD);
inc(pos, i + 1);
}
reverse(a.begin(), a.end());
}
reverse(S[1].begin(), S[1].end());
int ans = 0;
fore(i, 0, n)
ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 1)))));
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
const int INF = int(1e9);
const li INF64 = li(1e18);
const int N = 200 * 1000 + 555;
const int D = 7077;
int n, d, m;
int a[N], qs[N];
inline bool read() {
if(scanf("%d%d", &n, &d) != 2)
return false;
fore(i, 0, n)
scanf("%d", &a[i]);
assert(scanf("%d", &m) == 1);
fore(i, 0, m)
scanf("%d", &qs[i]);
return true;
}
bitset<D> L, R, cur;
int dist[N];
set<int> has;
void shiftL(int s, int t, int &uk) {
L <<= t - s;
for(; uk < n && a[uk] < t; uk++) {
if(t - a[uk] - 1 < D)
L[t - a[uk] - 1] = 1;
if(t - a[uk] < D)
L[t - a[uk]] = 1;
}
}
void shiftR(int s, int t, int &uk) {
R >>= t - s;
if(!has.count(t))
R[0] = 0;
for(; uk < n && a[uk] < t + D; uk++) {
if(a[uk] - t >= 0) {
R[a[uk] - t] = 1;
if(a[uk] - t + 1 >= 0)
R[a[uk] - t + 1] = 1;
}
}
}
inline void solve() {
fore(i, 0, m) {
dist[i] = INF;
int pos = int(lower_bound(a, a + n, qs[i]) - a);
if(pos > 0)
dist[i] = qs[i] - a[pos - 1] - 1;
if(pos < n)
dist[i] = min(dist[i], a[pos] - qs[i]);
}
has = set<int>(a, a + n);
int uL = 0, uR = 0;
L.reset();
R.reset();
fore(i, 0, m) {
shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL);
shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR);
double ans = atan2(1, dist[i]);
cur = L & R;
int pos = (int)cur._Find_first();
if(pos < D) {
int ds = pos;
ans = max(ans, 2 * atan2(1, ds));
}
printf("%.15f\n", ans);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}