N00Borz

2476

euuuammxzm

Ming_04

N00Borz
3天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e4+10;
int n,top;
int stk[N],vis[N];
struct Point{
double x,y;
bool operator<(const Point &o){
return x<o.x||(x==o.x&&y<o.y);
}
Point operator-(const Point &o){
return {x-o.x,y-o.y};
}
}a[N];
double dot(Point a,Point b)
{
return a.x*b.x+a.y*b.y;
}
double cross(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
}
double dist(Point a,Point b)
{
return sqrt(dot(a-b,a-b));
}
double area(Point a,Point b,Point c)
{
return cross(b-a,c-a);
}
double andrew()
{
sort(a,a+n);
for(int i=0;i<n;++i)
{
while(top>=2&&area(a[stk[top-1]],a[stk[top]],a[i])>0)
vis[stk[top--]]=0;
stk[++top]=i;
vis[i]=1;
}
vis[0]=false;
for(int i=n-1;i>=0;--i)
{
if(vis[i]) continue;
while(top>=2&&area(a[stk[top-1]],a[stk[top]],a[i])>0)
--top;
stk[++top]=i;
}
double res=0;
for(int i=2;i<=top;++i)
res+=dist(a[stk[i]],a[stk[i-1]]);
return res;
}
int main(void)
{
// sync;
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i].x>>a[i].y;
printf("%.2lf",andrew());
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_map>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
int a,b,p;
int bsgs(int a,int b,int p)
{
if(1%p==b%p) return 0;
int k=sqrt(p)+1;
unordered_map<int,int>hs;
for(int i=0,j=b%p;i<k;++i)
{
hs[j]=i;
j=1ll*j*a%p;
}
int ak=1;
for(int i=0;i<k;++i) ak=1ll*ak*a%p;
for(int i=1,j=ak;i<=k;++i)
{
if(hs.count(j)) return 1ll*i*k-hs[j];
j=1ll*j*ak%p;
}
return -1;
}
int main(void)
{
sync;
while(cin>>a>>p>>b,a||p||b)
{
int res=bsgs(a,b,p);
if(res==-1) cout<<"No Solution"<<endl;
else cout<<res<<endl;
}
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
ll mul(ll a,ll b,ll p)
{
ll res=0;
while(b)
{
if(b&1) res=(res+a)%p;
a=a*2%p;
b>>=1;
}
return res;
}
int main(void)
{
sync;
ll a,b,p;
cin>>a>>b>>p;
cout<<mul(a,b,p)<<endl;
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_set>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=210;
int n,m;
int f[N][N];
int sg(int x,int y)
{
if(~f[x][y]) return f[x][y];
int a[N];
mm(a,0);
for(int i=2;i<=x-2;++i) a[sg(i,y)^sg(x-i,y)]=1;
for(int i=2;i<=y-2;++i) a[sg(x,i)^sg(x,y-i)]=1;
for(int i=0;;++i) if(!a[i]) return f[x][y]=i;
}
int main(void)
{
sync;
mm(f,-1);
f[2][2]=f[2][3]=f[3][2]=0;
while(cin>>n>>m)
{
if(sg(n,m)) cout<<"WIN"<<endl;
else cout<<"LOSE"<<endl;
}
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e5+10;
int n;
int a[N],b[N],c[N];
inline void add(int p,int x){for(;p<=n;p+=p&-p) c[p]+=x;}
int qry(int p){int res=0;for(;p;p-=p&-p) res+=c[p];return res;}
int main(void)
{
sync;
cin>>n;
for(int i=2;i<=n;++i)
{
cin>>a[i];
}
for(int i=n;i>=1;--i)
{
int l=1,r=n+1;
while(l+1<r)
{
int m=(l+r)>>1;
if(qry(m-1)<=a[i]) l=m;
else r=m;
}
// cout<<i<<" "<<l<<" "<<qry(l)<<endl;
b[i]=l;
}
for(int i=1;i<=n;++i)
cout<<b[i]<<endl;
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=2e5+10;
int n;
int a[N],c[N],l[N],r[N];
int qry(int p){int res=0;for(;p;p-=p&-p) res+=c[p];return res;}
int main(void)
{
sync;
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n;++i)
{
l[i]=qry(a[i]);
}
mm(c,0);
for(int i=n;i>=1;--i)
{
r[i]=qry(a[i]);
}
ll res=0;
for(int i=2;i<n;++i)
res+=1ll*(i-1-l[i])*(n-i-r[i]);
cout<<res<<" ";
res=0;
for(int i=2;i<n;++i)
res+=1ll*l[i]*r[i];
cout<<res<<endl;
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=2e5+10;
int n,m,idx,tot;
int fa[N],dep[N];
struct node{
int l,r,x;
}q[N*40];
void upd(int &u,int v,int l,int r,int p,int x)
{
q[u=++tot]=q[v];
if(l==r) return void(q[u].x=x);
int m=(l+r)>>1;
if(p<=m) upd(q[u].l,q[v].l,l,m,p,x);
else upd(q[u].r,q[v].r,m+1,r,p,x);
}
int qry(int u,int l,int r,int p)
{
if(l==r) return q[u].x;
int m=(l+r)>>1;
if(p<=m) return qry(q[u].l,l,m,p);
else return qry(q[u].r,m+1,r,p);
}
int f(int x)
{
int fx=qry(fa[idx-1],1,n,x);
return fx==0?x:f(fx);
}
void unio(int x,int y)
{
x=f(x),y=f(y);
if(x==y)
{
fa[idx]=fa[idx-1];
dep[idx]=dep[idx-1];
}
else
{
int dx=qry(dep[idx-1],1,n,x);
int dy=qry(dep[idx-1],1,n,y);
if(dx<dy)
{
upd(fa[idx],fa[idx-1],1,n,x,y);
dep[idx]=dep[idx-1];
}
else if(dx>dy)
{
upd(fa[idx],fa[idx-1],1,n,y,x);
dep[idx]=dep[idx-1];
}
else
{
upd(fa[idx],fa[idx-1],1,n,x,y);
upd(dep[idx],dep[idx-1],1,n,y,dx+1);
}
}
}
int main(void)
{
sync;
cin>>n>>m;
int res=0;
while(m--)
{
++idx;
int op,a,b;
cin>>op;
if(op==1)
{
cin>>a>>b;
a^=res,b^=res;
unio(a,b);
}
else if(op==2)
{
cin>>a;
a^=res;
fa[idx]=fa[a];
dep[idx]=dep[a];
}
else
{
cin>>a>>b;
a^=res,b^=res;
fa[idx]=fa[idx-1];
dep[idx]=dep[idx-1];
res=(f(a)==f(b));
cout<<res<<endl;
}
}
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
int n,res,sum;
int a[10]={2,3,5,7,11,13,17,19,23,29};
void dfs(int p,int pre,int x,int s)
{
if(s>sum||(s==sum&&x<res))
{
res=x;
sum=s;
}
for(int i=1;i<=pre;++i)
{
if(1ll*x*a[p]>n) break;
x*=a[p];
dfs(p+1,i,x,s*(i+1));
}
}
int main(void)
{
sync;
cin>>n;
dfs(0,30,1,1);
cout<<res<<endl;
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;

int main(void)
{
sync;
int n,k;
cin>>n>>k;
ll res=1ll*n*k;
for(int l=1,r;l<=n&&k/l;l=r+1)
{
r=min(k/(k/l),n);
res-=1ll*(k/l)*(r-l+1)*(l+r)/2;
}
cout<<res<<endl;
return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!


N00Borz
2个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
vector<int> specialSort(int n) {
vector<int>res;
res.push_back(1);
for(int i=2;i<=n;++i)
{
int l=0,r=res.size()-1;
while(l<=r)
{
int m=(l+r)>>1;
if(compare(res[m],i)) l=m+1;
else r=m-1;
}
res.push_back(i);
for(int j=res.size()-2;j>r;--j)
swap(res[j],res[j+1]);
}
return res;
}
};