2.5万

winn
Asa_Ayato
77777777777

Dream_zsh
Perf

000_2

yxc的小迷弟
zzr0126

cl_2
wanghai673
15163669008
ZXG_DXX
Jun不见

2021-07-15 20:09
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10;
int st[N];
int ans[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
memset(st,0,sizeof st);
//memset(ans,0,sizeof ans);
for(int i=1;i<=n;i++){
int xx;
scanf("%d",&xx);
if(!st[xx])ans[xx]=i;
st[xx]++;
}
bool flag=0;
//cout<<"***";
for(int i=1;i<=n;i++){
if(st[i]==1){
cout<<ans[i]<<endl;
flag=1;
break;
}
}

if(!flag)cout<<-1<<endl;
}
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-07-08 18:16
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int w[N],idx;
int n,m;
int p[N];
int L[N],R[N];
int dist[N];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
bool cmp(int a,int b){
if(w[a]!=w[b])return w[a]<w[b];
return a<b;
}
int merge(int x,int y){
if(x==0||y==0)return x+y;
if(cmp(y,x))swap(x,y);
R[x]=merge(R[x],y);
if(dist[R[x]]>dist[L[x]])swap(R[x],L[x]);
dist[x]=dist[R[x]]+1;
return x;
}
int main(){
scanf("%d",&n);
w[0]=2e9;
while(n--){
int op;
scanf("%d",&op);
if(op==1){
int xx;
scanf("%d",&xx);
w[++idx]=xx;
dist[idx]=1;
p[idx]=idx;
}
else if(op==2){
int x,y;
scanf("%d%d",&x,&y);
int px=find(x); int py=find(y);
if(px!=py){
if(cmp(py,px))swap(px,py);
p[py]=px;
merge(px,py);
}
}
else if(op==3){
int x;
scanf("%d",&x);
cout<<w[find(x)]<<endl;
}
else {
int x;
scanf("%d",&x);
x=find(x);
if(cmp(R[x],L[x]))swap(L[x],R[x]);
p[x]=L[x]; p[L[x]]=L[x];
merge(L[x],R[x]);
}
}
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-05-26 17:59
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll w[N];
ll s[N];
int  n,m;
bool st[N];
int main(){
scanf("%d%d",&n,&m);
ll ans=0;
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
}
for(int i=1;i<=n;i++){
ll xx;
scanf("%lld",&xx);
st[i]=xx;
}
for(int i=1;i<=n;i++){
if(st[i])ans+=w[i],s[i]=s[i-1];
else s[i]=s[i-1]+w[i];
}
ll res=0;
for(int i=1;i<=n;i++){
int left=max(0,i-m);
res=max(res,s[i]-s[left]);
}
cout<<ans+res<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-05-26 17:49
#include<bits/stdc++.h>
using namespace std;
const int N=100100*31;
int son[N][2];
int cnt[N];
int idx;
int n,m;
void insert(int x,int v){
int p=0;
for(int i=30;i>=0;i--){
int xx=x>>i&1;
if(!son[p][xx])son[p][xx]=++idx;
p=son[p][xx];
cnt[p]+=v;
}
}
int query(int x){
int p=0; int res=0;
for(int i=30;i>=0;i--){
int xx=x>>i&1;
if(cnt[ son[p][!xx] ]){
p=son[p][!xx];
res=res<<1|1;
}
else {
p=son[p][xx];
res=res<<1;
}
}
return res;
}
int s[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int xx;
scanf("%d",&xx);
s[i]=s[i-1]^xx;
}
insert(s[0],1);
int ans=0;
for(int i=1;i<=n;i++){
if(i-m-1>=0)insert(s[i-m-1],-1);
ans=max(ans,query(s[i]));
insert(s[i],1);
}
cout<<ans<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-05-06 14:28

不能sizeof c c是形参，大小只有1 （因此，debug一小时）

memcpy(c,b,sizeof ss);


好像高除用的不是很多，，

#include<bits/stdc++.h>
using namespace std;
const int N=90,M=5;
typedef long long ll;

int f[N][N][M];
int n,m;
int ss[M];
ll t=0;
for(int i=0;i<M;i++){
t+=a[i]+b[i];
c[i]=t%100000000;
t/=100000000;
}
}
void  mul(int c[],int a[],int b){
ll t=0;
for(int i=0;i<M;i++){
t+=(ll)a[i]*b;
c[i]=t%100000000;
t/=100000000;
}
}
void  maxv(int c[],int a[],int b[]){
for(int i=M-1;i>=0;i--){
if(a[i]>b[i]){
memcpy(c,a,sizeof ss);
return ;
}
if(a[i]<b[i]){
memcpy(c,b,sizeof ss);
return ;
}
}
memcpy(c,b,sizeof ss);
return ;
}
void out(int c[]){
int k=M-1; bool flag=0;
while(k>=1&&!c[k])k--;
for(int i=k;i>=0;i--){
if(!flag)printf("%d",c[k]),flag=1;
else printf("%08d",c[i]);
}
cout<<endl;
}
int qmi2[N][M];
int a[N][N];
int main(){
scanf("%d%d",&n,&m);
qmi2[0][0]=1;
for(int i=1;i<=m;i++)mul(qmi2[i],qmi2[i-1],2);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
int ans[M]={0};
for(int i=1;i<=n;i++){
memset(f,0,sizeof f);
for(int len=1;len<=m;len++){
for(int l=1;l+len-1<=m;l++){
if(len==1){
mul(f[l][l],qmi2[m],a[i][l]);
continue;
}
int r=l+len-1;
int p=m-(r-l+1)+1;
int temp[M];
mul(temp,qmi2[p],a[i][r]);
maxv(f[l][r],f[l][r],temp);
mul(temp,qmi2[p],a[i][l]);
maxv(f[l][r],f[l][r],temp);
}
}
}
out(ans);
}


2021-04-27 15:51
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+100;
#define x first
#define y second
typedef pair<int,int>PII;
PII q[N];
int stk[N],top;
bool used[N];
int n;
PII operator-(PII a,PII b){
return {a.x-b.x,a.y-b.y};
}
PII operator+(PII a,PII b){
return {a.x+b.x,a.y+b.y};
}
int  operator*(PII a,PII b){
return a.x*b.y-a.y*b.x;
}
int get_dist(PII a,PII b){
int dx=a.x-b.x;
int dy=a.y-b.y;
return dx*dx+dy*dy;
}
int  area(PII a,PII b,PII c){
return (b-a)*(c-a);
}
void get_convex(){
sort(q,q+n);
for(int i=0;i<n;i++){
while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0){
if(area(q[stk[top-2]],q[stk[top-1]],q[i])<0)used[stk[--top]]=0;
else top--;
}
stk[top++]=i;
used[i]=1;
}
used[0]=0;
for(int i=n-1;i>=0;i--){
if(used[i])continue;
while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0)top--;
stk[top++]=i;
}
top--;
}
int rotating_calipers(){
if(top<=2)return get_dist(q[0],q[n-1]);
int res=0;
for(int i=0,j=2;i<top;i++){
PII d=q[stk[i]],e=q[stk[i+1]];
while(area(d,e,q[stk[j]])<area(d,e,q[stk[(j+1)]]))j=(j+1)%top;
res=max(res,get_dist(d,q[stk[j]]));
res=max(res,get_dist(e,q[stk[j]]));

}
return res;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d%d",&q[i].x,&q[i].y);
get_convex();
cout<<rotating_calipers()<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-04-27 11:22
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e4+10;
const double eps=1e-12;
const double pi=acos(-1);

typedef pair<double,double>PDD;
struct Circle {
PDD p;
double r;
};
PDD q[N];
int n;
int sign(double a){
if(fabs(a)<eps)return 0;
if(a<0)return -1;
else return 1;
}
int dcmp(double x,double y){
if(fabs(x-y)<eps)return 0;
if(x<y)return -1;
return 1;
}
PDD operator+(PDD a,PDD b){
return {a.x+b.x,a.y+b.y};
}
PDD operator-(PDD a,PDD b){
return {a.x-b.x,a.y-b.y};
}
PDD operator*(PDD a,double t){
return {a.x*t,a.y*t};
}
PDD operator/(PDD a,double  t){
return {a.x/t,a.y/t};
}
double operator*(PDD a,PDD b){
return a.x*b.y-a.y*b.x;
}
PDD rotate(PDD a,double b){
return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
pair<PDD,PDD> get_line(PDD a,PDD b){
return {(a+b)/2,rotate(b-a,pi/2)};
}
double get_dist(PDD a,PDD b){
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
auto u=p-q;
double t=w*u/(v*w);
return p+v*t;
}
Circle get_circle(PDD a,PDD b,PDD c){
auto u=get_line(a,b);
auto v=get_line(a,c);
PDD p=get_line_intersection(u.x,u.y,v.x,v.y);
return {p,get_dist(p,a)};
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf%lf",&q[i].x,&q[i].y);
}
double yy,xx;
scanf("%lf%lf",&yy,&xx);
for(int i=0;i<n;i++){
q[i]=rotate(q[i],yy/180.0*pi);
q[i].x/=xx;
}
random_shuffle(q, q + n);
Circle c={q[0],0};
for(int i=1;i<n;i++){
if(dcmp(c.r,get_dist(c.p,q[i]))<0){
c={q[i],0};
for(int j=0;j<i;j++){
if(dcmp(c.r,get_dist(c.p,q[j]))<0){
c={(q[i]+q[j])/2,get_dist(q[i],q[j])/2};
for(int k=0;k<j;k++){
if(dcmp(c.r,get_dist(c.p,q[k]))<0){
c=get_circle(q[i],q[j],q[k]);
}
}
}
}
}
}
//printf("%lf %lf\n",c.p.x,c.p.y);
printf("%.3lf\n",c.r);
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-04-26 19:16

get_mid(a,b) get_mid(b,c)就不能过 wc

Circle get_circle(PDD a,PDD b,PDD c){
auto xx=get_mid(a,b);
auto yy=get_mid(a,c);
PDD res=get_line_intersection(xx.x,xx.y,yy.x,yy.y);
return {res,get_dist(res,b)};
}

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<double ,double>PDD;
const int N=1e5+100;
const double  pi=acos(-1);
const double  eps=1e-12;
struct Line{
PDD st,ed;
}line[N];
struct Circle{
PDD p;
double r;
};
PDD q[N];
PDD operator- (PDD a,PDD b){
return {a.x-b.x,a.y-b.y};
}
PDD operator+ (PDD a,PDD b){
return {a.x+b.x,a.y+b.y};
}
PDD operator*(PDD a,double t){
return {a.x*t,a.y*t};
}
double get_dist(PDD a,PDD b){
double dx=a.x-b.x;
double dy=a.y-b.y;
return  sqrt(dx*dx+dy*dy);
}
double  operator*(PDD a,PDD b){
return a.x*b.y-a.y*b.x;
}
PDD operator/(PDD a,double b){
return {a.x/b,a.y/b};
}
int  sign(double x){
if(fabs(x)<eps)return 0;
if(x<0)return -1;
return 1;
}
int  dcmp(double x,double y){
if(fabs(x-y)<eps)return 0;
if(x<y)return -1;
return 1;
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
PDD u=p-q;
double t=w*u/(v*w);
//return {p.x+v.x*t,p.y+v.y*t};
return p+v*t;
}
PDD rotate(PDD a,double b){
return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
pair<PDD,PDD>  get_mid(PDD a,PDD b){
return {(a+b)/2,rotate(b-a,pi/2)};
}
Circle get_circle(PDD a,PDD b,PDD c){
auto xx=get_mid(a,b);
auto yy=get_mid(a,c);
PDD res=get_line_intersection(xx.x,xx.y,yy.x,yy.y);
return {res,get_dist(res,b)};
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf%lf",&q[i].x,&q[i].y);
}
random_shuffle(q, q + n);
Circle c={q[0],0};
for(int i=0;i<n;i++){
if(dcmp(c.r,get_dist(c.p,q[i]))<0){
c={q[i],0};
for(int j=0;j<i;j++){
if(dcmp(c.r,get_dist(c.p,q[j]))<0){
c={{(q[i]+q[j])/2},get_dist(q[i],q[j])/2};
for(int k=0;k<j;k++){
if(dcmp(c.r,get_dist(c.p,q[k]))<0){
c=get_circle(q[i],q[j],q[k]);
}
}
}
}
}
}
printf("%.10lf\n",c.r);
printf("%.10lf %.10lf\n",c.p.x,c.p.y);
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-04-26 17:00
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=10010;
typedef long double LD;
typedef pair<LD,LD>PDD;
typedef pair<int,int>PII;
const LD eps=1e-18;
struct Line {
PDD st,ed;
vector<int>ids;
}line[N];
int cnt;
int q[N];
int ans[N];
PDD operator-(PDD a,PDD b){
return {a.x-b.x,a.y-b.y};
}
int ki[N],vi[N];
int sign(LD x){
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
}
int dcmp(LD x,LD y){
if(fabs(x-y)<eps)return 0;
if(x>y)return 1;
else return -1;
}
LD cross(PDD a,PDD b){
return a.x*b.y-a.y*b.x;
}
LD area(PDD a,PDD b,PDD c){
return cross(b-a,c-a);
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
PDD u=p-q;
LD t=cross(w,u)/cross(v,w);
return {p.x+t*v.x,p.y+t*v.y};
}
PDD get_line_intersection(Line a,Line b){
return  get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}
LD get_angle(const  Line  &a){
return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}
bool cmp(const Line &a,const Line &b){
LD A=get_angle(a),B=get_angle(b);
if(!dcmp(A,B))return sign(area(a.st,a.ed,b.st))<0;
return A<B;
}
bool on_right(Line a,Line b,Line c){
PDD o=get_line_intersection(b,c);
return area(a.st,a.ed,o)<0;
}
void half_plane_intersection(){
sort(line,line+cnt,cmp);
int hh=0,tt=-1;
for(int i=0;i<cnt;i++){
if(i&&!dcmp(get_angle(line[i-1]),get_angle(line[i])))continue;
while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]]))tt--;
while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]]))hh++;
q[++tt]=i;
}
while(hh+1<=tt&&on_right(line[q[hh]],line[q[tt-1]],line[q[tt]]))tt--;
while(hh+1<=tt&&on_right(line[q[tt]],line[q[hh]],line[q[hh+1]]))hh++;
int k=0;
for(int i=hh;i<=tt;i++){
for(auto  t:line[q[i]].ids){
ans[k++]=t;
}
}
sort(ans,ans+k);
cout<<k<<endl;
for(int i=0;i<k;i++)cout<<ans[i]<<' ';
cout<<endl;
}
int main(){
map<PII,vector<int> >ids;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&ki[i]);
for(int i=1;i<=n;i++)scanf("%d",&vi[i]);
for(int i=1;i<=n;i++){
ids[{ki[i],vi[i]}].push_back(i);
}
line[cnt++]={{0,10000},{0,0}};
line[cnt++]={{0,0},{10000,0}};
map<PII,vector<int> >::iterator it;

for(it=ids.begin();it!=ids.end();it++){
line[cnt++]={{0,it->first.first},{1,it->first.first+it->first.second},it->second};
}
half_plane_intersection();
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2021-04-26 14:31
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=510;
const double eps=1e-8;
typedef pair<double ,double>PDD;
struct Line{
PDD st,ed;
}line[N];
PDD pg[N],ans[N];
int q[N];
int cnt;
int sign(double x){
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
}
int dcmp(double x,double y){
if(fabs(x-y)<eps)return 0;
if(x>y)return 1;
return -1;
}
PDD operator-( PDD a,PDD b){
return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b){
return a.x*b.y-a.y*b.x;
}
double get_angle(const Line &a){
return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}
double area(PDD a,PDD b,PDD c){
return cross(b-a,c-a);
}
bool cmp(const Line &a,const Line &b){
double A=get_angle(a); double B=get_angle(b);
if(!dcmp(A,B))return area(a.st,a.ed,b.st)<0;
return A<B;
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
PDD u=p-q;
double t=cross(w,u)/cross(v,w);
return {p.x+t*v.x,p.y+t*v.y};
}
PDD get_line_intersection(Line a,Line b){
return get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}
bool on_right(Line &a,Line &b,Line &c){
PDD o=get_line_intersection(b,c);
return sign(area(a.st,a.ed,o))<=0;
}
double half_plane_intersection(){
sort(line,line+cnt,cmp);
int hh=0,tt=-1;
for(int i=0;i<cnt;i++){
if(i&&!dcmp(get_angle(line[i]),get_angle(line[i-1])))continue;
while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]]))tt--;
while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]]))hh++;
q[++tt]=i;
}
while(hh+1<=tt&&on_right(line[q[hh]],line[q[tt-1]],line[q[tt]]))tt--;
while(hh+1<=tt&&on_right(line[q[tt]],line[q[hh]],line[q[hh+1]]))hh++;
q[++tt]=q[hh];
int k=0;
for(int i=hh;i+1<=tt;i++){
ans[k++]=get_line_intersection(line[q[i]],line[q[i+1]]);
}
double res=0;
for(int i=1;i+1<k;i++){
res+=area(ans[0],ans[i],ans[i+1]);
}
return res/2;
}
int main(){
int n,m;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%lf%lf",&pg[i].x,&pg[i].y);
}
for(int i=0;i<m;i++){
line[cnt++]={pg[i],pg[(i+1)%m]};
}
}
double res=half_plane_intersection();
printf("%.3lf\n",res);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~