idea: Cocoly1990
Solution
Tutorial is loading...
Code
By Imakf
#include <iostream>
void solve(){
int n; std::cin >> n;
for(int i = 1 ,nouse ; i <= n ; ++i){
std::cin >> nouse;
}
std::cout << "1 " << n << std::endl;
}
int main(){
int t; std::cin >> t;
while(t--) solve();
return 0;
}
1764B - Doremy's Perfect Math Class
idea: waaitg
Solution
Tutorial is loading...
Code
By waaitg
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int a[maxn];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int tmp=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
tmp=gcd(tmp,a[i]);
}
printf("%d\n",a[n]/tmp+(a[1]==0));
}
return 0;
}
1764C - Doremy's City Construction
idea: waaitg
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
static char q[64];int cnt=0;
if(x==0)return pc('0'),void();
if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=200005;
int a[maxn];
int main(){
int t;read(t);
while(t--){
int n;read(n);
for(int i=1;i<=n;++i)
read(a[i]);
sort(a+1,a+n+1);
if(a[1]==a[n]){
write(n/2),pc('\n');
continue;
}
long long ans=0;
for(int l=1,r=1;l<=n;l=r=r+1){
while(r+1<=n&&a[r+1]==a[l])++r;
ans=max(ans,1ll*(n-r)*r);
}
write(ans),pc('\n');
}
return 0;
}
idea: Imakf
Solution
Tutorial is loading...
Code
By Imakf
#include <cstdio>
#include <iostream>
#define LL long long
const int MX = 5000 + 233;
LL C[MX][MX] ,n ,p ,fac[MX];
void init(){
for(int i = 0 ; i < MX ; ++i) C[i][0] = 1;
for(int i = 1 ; i < MX ; ++i)
for(int j = 1 ; j < MX ; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
fac[0] = fac[1] = 1 % p;
for(int i = 2 ; i < MX ; ++i) fac[i] = fac[i - 1] * i % p;
}
int main(){
std::cin >> n >> p;
init();
int t = n / 2;
LL Ans = 0;
for(int i = t ; i <= n - 1 ; ++i){
if((n & 1) && i == n - 1) break;
int upper = (i == n - 1) ? n - i - 1 : n - i - 2;
for(int j = 0 ; j <= upper ; ++j){
Ans = (Ans + n * (2 * t - i) * C[upper][j] % p * fac[j + i - 1]) % p;
}
}
std::cout << Ans << std::endl;
return 0;
}
idea: Imakf
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 2e5 + 5;
int n ,s;
struct Goat{
int x ,y ,id;
}A[MX];
bool cmp(Goat a ,Goat b){
return a.x < b.x;
}
int mx[MX];
int calc(int id){
if(id == 1) return A[id].x;
int far = std::max(calc(id - 1) ,mx[id - 2]);
return std::max(std::min(far ,A[id].x) + A[id].y ,A[id].x);
}
int ans[MX];
void solve(){
scanf("%d%d" ,&n ,&s);
for(int i = 1 ,x ,y ; i <= n ; ++i){
scanf("%d%d" ,&x ,&y);
A[i] = (Goat){x ,y ,i};
ans[i] = false;
}
std::sort(A + 1 ,A + 1 + n ,cmp);
for(int i = 1 ; i <= n ; ++i){
mx[i] = std::max(A[i].x + A[i].y ,mx[i - 1]);
}
for(int i = 1 ; i < n ; ++i){
if(A[i].x + A[i].y >= s){
ans[A[i].id] = true;
}
}
if(calc(n) >= s) ans[A[n].id] = true;
puts(ans[1] ? "YES" : "NO");
}
int main(){
int t; scanf("%d" ,&t);
while(t--) solve();
return 0;
}
1764F - Doremy's Experimental Tree
idea: Cocoly1990
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 3e3 + 5;
bool vis[MX];
LL w[MX][MX] ,dis[MX];
std::vector<int> e[MX];
int size[MX];
void dfs(int x ,int f){
size[x] = 1;
for(auto i : e[x]){
if(i == f) continue;
dfs(i ,x);
size[x] += size[i];
}
for(auto i : e[x]){
if(i == f) continue;
printf("%d %d %lld\n" ,x ,i ,(w[1][x] - w[1][i]) / size[i]);
}
}
int main(){
int n; scanf("%d" ,&n);
memset(w ,-0x3f ,sizeof w);
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= i ; ++j){
scanf("%lld" ,&w[i][j]);
w[j][i] = w[i][j];
}
}
memset(dis ,-0x3f ,sizeof dis);
dis[1] = 0;
for(int i = 1 ; i <= n ; ++i){
int x = 0;
for(int j = 1 ; j <= n ; ++j){
if(!vis[j] && (!x || dis[j] > dis[x])){
x = j;
}
}
//debug("x = %d " ,x);
//ans += dis[x];
if(i != 1) for(int j = 1 ; j <= n ; ++j){
if(w[j][x] == dis[x] && vis[j]){
e[x].push_back(j);
e[j].push_back(x);
//debug("%d %d\n" ,x ,j);
}
}
vis[x] = true;
for(int j = 1 ; j <= n ; ++j){
dis[j] = std::max(dis[j] ,w[x][j]);
}
}
//return 0;
dfs(1 ,1);
return 0;
}
1764G3 - Doremy's Perfect DS Class (Hard Version)
idea: waaitg
Solution
Tutorial is loading...
G1 Code
By Imakf
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::map<std::pair<int, int>, int> M;
int n;
int query(int l, int r, int k = 2) {
if (l == r) return 1;
if (l == 1 && r == n) {
return n / k + 1;
}
if (k == 2 && M.count(make_pair(l, r)))
return M[make_pair(l, r)];
printf("? %d %d %d\n",l ,r, k);
fflush(stdout);
int x;
scanf("%d", &x);
if (k == 2) {
M[make_pair(l, r)] = x;
}
return x;
}
void answer(int x) {
printf("! %d\n", x);
fflush(stdout);
exit(0);
}
int main() {
scanf("%d", &n);
int npos = 0;
if (n % 2 == 0) {
int l = 1, r = n, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (query(1, mid, n) == 2) {
r = mid - 1;
} else {
l = mid + 1;
}
npos = r + 1;
}
}
//answer(npos);
//if (n & 1) {
int l = 1, r = n - 1, mid;
while (l <= r) {
debug("[%d ,%d]\n",l ,r);
mid = (l + r) >> 1;
int lq = 2 * query(1, mid) - (mid - 1 + 1);
int rq = 2 * query(mid + 1, n) - (n - (mid + 1) + 1);
if (npos) {
if (npos <= mid) --lq;
else --rq;
}
if (lq > rq) {
r = mid - 1;
} else {
l = mid + 1;
}
}
// cut [r + 1, r + 2]
++r;
// now cut [r, r + 1]
answer(r);
// }
}
G3 Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int query(int l,int r,int k){
printf("? %d %d %d\n",l,r,k);
fflush(stdout);int re;scanf("%d",&re);
return re;
}
void answer(int x){
printf("! %d\n",x);
fflush(stdout);
}
int rt=-1;
void divide(int l,int r,int l1,int l2,int r1,int r2){
if(l==r){
answer(l);
return;
}
if(l+1==r){
if(r1==r2+1){
if(query(r,n,2)==r2+1)answer(r);
else answer(l);
}
else if(l1==l2+1){
if(query(1,l,2)==l2+1)answer(l);
else answer(r);
}
else{
if(l>1){
if(query(1,l,n)==2)answer(r);
else answer(l);
}
else{
if(query(r,n,n)==2)answer(l);
else answer(r);
}
}
return;
}
int mid=(l+r)>>1;
int L=query(1,mid,2),R=query(mid+1,n,2);
if(L*2-mid>R*2-(n-mid))divide(l,mid,L,l2,r1,R);
else if(L*2-mid<R*2-(n-mid))divide(mid+1,r,l1,L,R,r2);
else{
if(~rt){
if(rt)divide(l,mid,L,l2,r1,R);
else divide(mid+1,r,l1,L,R,r2);
}
if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2);
else rt=1,divide(l,mid,L,l2,r1,R);
}
}
int main(){
scanf("%d",&n);
divide(1,n,n/2+1,0,n/2+1,0);
return 0;
}
1764H - Doremy's Paint 2 idea: Imakf, waaitg and errorgorn
Solution
Tutorial is loading...
Code
By errorgorn
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m,k;
ii arr[600005];
int ans[400005];
vector<int> uni;
int nxt[200005];
int state[200005];
int state2[200005];
bool has(int l,int r,set<int> &s){
auto it=s.lb(l);
return *it<r;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m>>k;
rep(x,0,m) cin>>arr[x].fi>>arr[x].se;
rep(x,0,m) arr[x].fi--,arr[x].se--;
rep(x,0,2*m) arr[x+m]=arr[x];
int l=0;
while (l<m){
uni={0,n};
rep(x,l,l+2*k) uni.pub(arr[x].fi),uni.pub(arr[x].se+1);
sort(all(uni)); uni.erase(unique(all(uni)),uni.end());
rep(x,0,sz(uni)-1) nxt[uni[x]]=uni[x+1];
set<ii> s; for (auto it:uni) s.insert({it,it}); //position, color
rep(x,0,sz(uni)) state[uni[x]]=state2[uni[x]]=1;
vector<iii> proc; //time, position, state
rep(x,l+k,l+2*k){
if (s.count({arr[x].fi,arr[x].fi}) && state[arr[x].fi]){
proc.pub({x,arr[x].fi,state[arr[x].fi]});
state[arr[x].fi]=0;
}
while (true){
auto it=s.ub(ii(arr[x].fi,1e9));
if ((*it).fi>arr[x].se) break;
if (arr[x].se+1<(*next(it)).fi) s.insert({arr[x].se+1,(*it).se});
else{
proc.pub({x,(*it).se,state[(*it).se]});
state[(*it).se]=0;
}
s.erase(it);
}
}
int curr=0;
set<int> pos={n};
for (auto [a,b]:s) if (b!=n){
curr++;
if (state[b]) curr+=nxt[b]-b-1;
pos.insert(b);
}
s.clear(); for (auto it:uni) s.insert({it,it}); //color, position
set<ii> ranges; rep(x,0,sz(uni)-1) ranges.insert({uni[x],uni[x+1]});
rep(x,l+k,l){
//merge things
auto it=s.lb({arr[x].fi,-1});
vector<int> v={(*it).se};
while ((*it).fi<=arr[x].se){
it=next(it);
s.erase(prev(it));
v.pub((*it).se);
}
if (sz(v)>1){
rep(x,0,sz(v)-1){
if (state[v[x]] && state2[v[x]]) curr-=v[x+1]-v[x]-1;
state2[v[x]]=0;
curr-=has(v[x],v[x+1],pos);
ranges.erase({v[x],v[x+1]});
}
curr+=has(v[0],v[sz(v)-1],pos);
s.insert({arr[x].fi,v[0]});
ranges.insert({v[0],v[sz(v)-1]});
}
while (!proc.empty() && get<0>(proc.back())==x+k){
int a,b,c; tie(a,b,c)=proc.back(); proc.pob();
if (c){
state[b]=c;
if (state[b] && state2[b]) curr+=nxt[b]-b-1;
}
if (!pos.count(b)){
auto it=prev(ranges.ub({b,1e9}));
int l,r; tie(l,r)=*it;
if (!has(l,r,pos)) curr++;
pos.insert(b);
}
}
ans[x]=curr;
}
l+=k;
}
rep(x,0,m) cout<<ans[x]<<" "; cout<<endl;
}