UOJ Logo l___z___t的博客

博客

标签
暂无

蒟蒻的垃圾程序

2018-10-16 16:34:26 By l___z___t

T1

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct lzt{
    int st,len;
    bool operator < (lzt ano) const{
        if(len/2!=ano.len/2){
            return len/2>ano.len/2;
        }
        return st<ano.st;
    }
};

lzt mp(int x,int y){
    return (lzt){x,y};
}

int n,m;
set<lzt> s;
set<int> b;
int L,R;
int p[1000100];

void work(){
    n=read();m=read();
    L=-1;R=-1;
    rep(i,1,m){
        int op=read(),x=read();
        if(op==1){
            int len=0,pos=0;
            if(L==-1){
                len=1;pos=1;
                p[x]=pos;
                L=1;R=1;
            }
            else{
                if(L>=n-R+1){
                    len=L;pos=1;
                }
                else{
                    len=n-R+1;pos=n;
                }
                if(s.empty()){
                    p[x]=pos;
                    if(pos<L){
                        s.insert(mp(pos,L-pos));
                        L=pos;
                    }
                    else{
                        s.insert(mp(L,pos-L));
                        R=pos;
                    }
                }
                else{
                    lzt nw=*s.begin();
                    int md=nw.st+nw.len/2;
                    int dis=md-nw.st+1;
                    if(len<dis || len==dis&&pos>=md){
                        len=dis;pos=md;
                    }
                    p[x]=pos;
                    if(pos==1){
                        s.insert(mp(pos,L-pos));
                        L=pos;
                    }
                    else if(pos==n){
                        s.insert(mp(R,pos-R));
                        R=pos;
                    }
                    else{
                        s.erase(s.begin());
                        int l=nw.st,r=nw.st+nw.len;
                        s.insert(mp(l,pos-l));
                        s.insert(mp(pos,r-pos));
                    }
                }
            }
            printf("%d\n",p[x]);
            b.insert(p[x]);
        }
        else{
            int pos=p[x];
            p[x]=0;
            set<int>::iterator IT=b.find(pos);
            if(s.empty()){
                L=-1;R=-1;
            }
            else{
                if(pos==L){
                    IT++;
                    L=*IT;
                    s.erase(mp(pos,L-pos));
                }
                else if(pos==R){
                    IT--;
                    R=*IT;
                    s.erase(mp(R,pos-R));
                }
                else{
                    IT++;int nxt=*IT;
                    IT--;IT--;int pre=*IT;
                    s.erase(mp(pre,pos-pre));
                    s.erase(mp(pos,nxt-pos));
                    s.insert(mp(pre,nxt-pre));
                }
            }
            b.erase(pos);
        }
        // for(set<lzt>::iterator it=s.begin();it!=s.end();it++){
            // cout<<(*it).st<<' '<<(*it).len<<endl;
        // }
        // cout<<endl;
    }
}

int main(){
    #ifdef LZT
        freopen("A.in","r",stdin);
    #endif

    work();

    #ifdef LZT
        Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
    #endif
}

T2

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int maxn=1010;
int n;
string s[maxn];

bool cmp(string a,string b){
    string c=a+b,d=b+a;
    return c>d;
}

void work(){
    n=read();
    rep(i,1,n) cin>>s[i];
    sort(s+1,s+n+1,cmp);
    rep(i,1,n) cout<<s[i];
}

int main(){
    #ifdef LZT
        freopen("B.in","r",stdin);
        freopen("B.out","w",stdout);
    #endif

    work();

    #ifdef LZT
        Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
    #endif
}

T3

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const double eps=1e-9;
const int maxn=100100;
int n,m;
double dis[maxn*3];
vector<pii> G[maxn*3];

double calc(double d,int t){
    if(t==0) return d;
    else if(t==1) return 1.0/(d-1);
    else if(t==2) return (d-1)/d;
}

void work(){
    n=read(),m=read();
    rep(i,1,n*3) dis[i]=1e9;
    rep(i,1,m){
        int x=read(),y=read(),l=read();
        G[x].pb(mp(y+n,l));
        G[y].pb(mp(x+n,l));
        G[x+n].pb(mp(y+n+n,l));
        G[y+n].pb(mp(x+n+n,l));
        G[x+n+n].pb(mp(y,l));
        G[y+n+n].pb(mp(x,l));
    }
    dis[1]=0;
    priority_queue<pair<pair<double,int>,int>,vector<pair<pair<double,int>,int> >,greater<pair<pair<double,int>,int> > > pq;
    pq.push(mp(mp(0,0),1));
    while(!pq.empty()){
        pair<pair<double,int>,int> nw=pq.top();pq.pop();
        if(fabs(nw.fi.fi-dis[nw.se])>eps) continue;
        for(int i=0;i<G[nw.se].size();i++){
            int v=G[nw.se][i].fi;
            double dist=calc(G[nw.se][i].se,nw.fi.se);
            int nwt=nw.fi.se+1;if(nwt==3) nwt=0;
            if(dis[v]>dist+dis[nw.se]){
                dis[v]=dist+dis[nw.se];
                pq.push(mp(mp(dis[v],nwt),v));
            }
        }
    }
    // rep(i,1,n) printf("%.3f %.3f %.3f\n",dis[i],dis[n+i],dis[n+n+i]);
    double ans=min(min(dis[n],dis[n+n]),dis[n+n+n]);
    if(ans>=1e9) puts("chu ti ren shi zhi zhang");
    else printf("%.3f\n",ans);
}

int main(){
    #ifdef LZT
        freopen("C.in","r",stdin);
        freopen("C.out","w",stdout);
    #endif

    work();

    #ifdef LZT
        Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
    #endif
}
共 1 篇博客

中文 English

Server time: 2024-11-24 22:30:07   |   浙ICP备17047493号