CCSP比赛记录(299.896555分)

可能赢了

可能没赢

UPD:赢了,爽啊。。谁知道第二名多少分?

比赛体验一般。没人回答问题,评测queue长达15分钟。

#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '"' + s + '"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? "true" : "false");}string to_string(vector<bool> v) {  bool first = true;  string res = "{";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(v[i]);  }  res += "}";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = "";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = "{";  for (const auto &x : v) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(x);  }  res += "}";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << " " << to_string(H);  debug_out(T...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

int n,l,m,cap,vc[2020];
struct edge{
    int to,tc;
    double cost;
};
vector<edge> edges[2020];

double md[10000010];
int fr[10000010];

int main() {
    read(n,l,m,cap);
    cout<<setprecision(6)<<fixed;
    for(int i=1;i<=l;i++){
        read(vc[i]);
    }
    for(int i=1;i<=m;i++){
        int fr,to,co;
        double prob;
        scanf("%d%d%lf%d",&fr,&to,&prob,&co);
        if(prob!=1) edges[fr].PB({to,co,-log(1-prob)});
        else edges[fr].PB({to,co,1e8});
    }
    for(int i=0;i<10000010;i++)md[i] = 1e18;
    priority_queue<pdi,vector<pdi>,greater<pdi>> Pq;
    Pq.push(MP(0.0,0));
    md[0] = 0;
    while(!Pq.empty()){
        pdi C = Pq.top();Pq.pop();
        if(C.F>md[C.S])continue;
        int a = (C.S>5000000),b = C.S-(a?5000000:0),c = b%2001,d = b/2001;
        if(a && d == 0){
            vector<int> V;
            int ct = C.S;
            int id = 0;
            while(ct!=0){
                int C = (ct%5000000)/2001;
                if(V.size() && V.back() == C){
                    id = C;
                }else{
                    V.PB(C);
                }
                ct = fr[ct];
            }
            V.PB(ct);
            reverse(all(V));
            cout<<id<<endl;
            cout<<c<<endl;
            cout<<1.0-exp(-C.F)<<endl;
            for(int i=0;i<V.size();i++){
                cout<<V[i]<<" \n"[i == V.size()-1];    
            }
            return 0;
        }
        if(!a && d<=l && d>=1 && c+vc[d]<=cap){
            int tgt = C.S+5000000+vc[d];
            if(md[tgt]>C.F){
                md[tgt] = C.F;
                fr[tgt] = C.S;
                Pq.push(MP(C.F,tgt));
            }
        }
        for(auto ct:edges[d]){
            if(c+ct.tc>cap)continue;
            int tgt = ct.to*2001+c+ct.tc+(a?5000000:0);
            if(md[tgt]>C.F+ct.cost){
                md[tgt] = C.F+ct.cost;
                fr[tgt] = C.S;
                Pq.push(MP(C.F+ct.cost,tgt));
            }
        }
    }
    return 0;
}
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '"' + s + '"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? "true" : "false");}string to_string(vector<bool> v) {  bool first = true;  string res = "{";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(v[i]);  }  res += "}";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = "";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = "{";  for (const auto &x : v) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(x);  }  res += "}";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << " " << to_string(H);  debug_out(T...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

string Fsys[18000000];

int Fcnt = 0;
int filemp[5050][5050];
bool fileown[5050][5050];
bool cmp[5050][5050];

map<string,int> Files,Commits;
string Fname[5050];

char op[150],name[150],name1[150],name2[150],File[400];

int N,offset,len;
int wcmt = 0,wcac = 1,cac_emp = 1;

void Mgtline(char *Tgt){
    while(1){
        char ch= getchar();
        if(ch == '\n'){
            *Tgt = 0;
            return;
        }else{
            *Tgt = ch;
            Tgt++;
        }
    }
}

void make_cac(){
    if(!cac_emp)return;
    cac_emp = 0;
    int T = Files.size();
    for(int i=1;i<=T;i++){
        filemp[wcac][i] = filemp[wcmt][i];
    }
}

int main() {
    read(N);
    for(int opn = 1;opn<=N;opn++){
        scanf("%s",op);
        if(op[0] == 'w'){
            make_cac();
            scanf("%s",name);
            read(offset,len);
            string Sname(name);
            if(!Files.count(Sname)){
                int cnid = Files.size()+1;
                Files[Sname] = cnid;
                Fname[cnid] = Sname;
                for(int j=1;j<cnid;j++){
                    cmp[j][cnid] = Fname[j]>Fname[cnid];
                    cmp[cnid][j] = !cmp[j][cnid];
                }
            }
            int FNid = Files[Sname];
            int Fid = filemp[wcac][FNid];
            
            if(Fid<=0){
                Fid = ++Fcnt;
                filemp[wcac][FNid] = Fid;
                fileown[wcac][FNid] = 1;
            }
            if(!fileown[wcac][FNid]){
                Fid = ++Fcnt;
                Fsys[Fid] = Fsys[filemp[wcac][FNid]];
                filemp[wcac][FNid] = Fid;
                fileown[wcac][FNid] = 1;
            }
            if(Fsys[Fid].length()<offset+len)Fsys[Fid].resize(offset+len,'.');
            Mgtline(File);
            for(int i=0;i<len;i++)Fsys[Fid][offset+i] = File[i];
        }
        if(op[0] == 'r'){
            scanf("%s",name);
            read(offset,len);
            string Sname(name);
            if(!Files.count(Sname)){
                for(int i=0;i<len;i++)putchar('.');
                putchar('\n');
                continue;
            }
            int FNid = Files[Sname];
            int Fid = filemp[wcac][FNid]?filemp[wcac][FNid]:filemp[wcmt][FNid];
            if(Fid<=0){
                for(int i=0;i<len;i++)putchar('.');
                putchar('\n');
                continue;
            }
            for(int i=0;i<len;i++)putchar((offset+i)<Fsys[Fid].size()?Fsys[Fid][offset+i]:'.');
            putchar('\n');
        }
        if(op[0] == 'u'){
            scanf("%s",name);
            string Sname(name);
            if(!Files.count(Sname)){
                continue;
            }
            int FNid = Files[Sname];
            int Fid = filemp[wcac][FNid]?filemp[wcac][FNid]:filemp[wcmt][FNid];
            if(Fid<=0) continue;
            make_cac();
            ++Fcnt;
            filemp[wcac][FNid] = -Fcnt;
        }
        if(op[0] == 'l'){
            int t = Files.size();
            int cnt = 0,mi,mx;
            for(int i=1;i<=t;i++){
                int Fid = filemp[wcac][i]?filemp[wcac][i]:filemp[wcmt][i];
                if(Fid<=0) continue;
                cnt+=1;
                if(cnt == 1){
                    mi = mx = i;
                }else{
                    if(cmp[mi][i])mi = i;
                    if(cmp[i][mx])mx = i;
                }
            }
            if(cnt == 0)cout<<"0\n";
            else{
                cout<<cnt<<' '<<Fname[mi]<<' '<<Fname[mx]<<"\n";
            }
        }
        if(op[0] == 'c' && op[1] == 'o'){
            scanf("%s",name);
            string Sname(name);
            if(Commits.count(Sname) || cac_emp){
                debug("Commit Skipped");
                continue;
            }
            Commits[Sname] = wcac;
            wcmt = wcac;
            wcac = Commits.size()+1;
            cac_emp = 1;
        }
        if(op[0] == 'c' && op[1] == 'h'){
            scanf("%s",name);
            string Sname(name);
            if(!Commits.count(Sname) || !cac_emp){
                debug("Checkout Skipped");
                continue;
            }
            wcmt = Commits[Sname];
        }
        if(op[0] == 'm'){
            scanf("%s%s",name1,name2);
            string S1(name1),S2(name2);
            if(Commits.count(S2) || !Commits.count(S1) || Commits[S1] == wcmt || !cac_emp){
                debug("Merge Skipped");
                continue;
            }
            int wcmt2 = Commits[S1];
            int T = Files.size();
            for(int i=1;i<=T;i++){
                if(abs(filemp[wcmt][i])>abs(filemp[wcmt2][i])) filemp[wcac][i] = filemp[wcmt][i];
                else filemp[wcac][i] = filemp[wcmt2][i];
            }
            Commits[S2] = wcac;
            wcmt = wcac;
            wcac = Commits.size()+1;
            cac_emp = 1;
        }
    }
    return 0;
}
#include "gc.h"

#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '"' + s + '"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? "true" : "false");}string to_string(vector<bool> v) {  bool first = true;  string res = "{";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(v[i]);  }  res += "}";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = "";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = "{";  for (const auto &x : v) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(x);  }  res += "}";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << " " << to_string(H);  debug_out(T...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

using namespace std;

bool vis[1024] = {0};

void gc(unsigned char *mem) {
    unsigned char *opt = mem;
    static unsigned char nmem[1024*1024*64];
    int Rn = *((int*)mem);
    queue<int> Q2;
    debug(Rn);
    for(int i=0;i<Rn;i++){
        int pt = ((int*)mem)[i+1];
        debug(pt);
        Q2.push(pt);
    }
    mem+=4*(Rn+1);
    int Tn = *((int*)mem);
    debug(Tn);
    mem+=4;
    vector<int> Tmap[1024][4];
    bool vis[1024] = {0};
    int rewire[1024] = {0};
    for(int i=0;i<Tn;i++){
        int tnt = *((int*)mem);
        debug(tnt);
        mem+=4;
        int cp = 0;
        for(int j=0;j<tnt;j++){
            debug((int)mem[j],cp);
            if(mem[j] == 0){
                Tmap[i][mem[j]].PB(cp);
                cp+=1;
            }
            if(mem[j] == 1){
                if(cp&1)cp+=1;
                Tmap[i][mem[j]].PB(cp);
                cp+=2;
            }
            if(mem[j] >= 2){
                if(cp&3)cp+=4-(cp&3);
                Tmap[i][mem[j]].PB(cp);
                cp+=4;
            }
        }
        mem+=tnt;
    }
    int Hl = *((int*)mem);
    debug(Hl);
    mem+=4;
    unsigned char *old_heap = mem;
    int sz = 0;
    vector<int> wupd_pointers,wupd_clsname;
    queue<int> Q;
    while(!Q2.empty()){
        int C = Q2.front();Q2.pop();
        *((int*)(mem+C)) = *((int*)(mem+C))+2048;
        Q.push(C);
    }
    while(!Q.empty()){
        debug(Q.size());
        int C = Q.front();Q.pop();
        debug(1);
        int typ = *((int*)(mem+C));
        assert(typ<134217728);
        typ = typ&2047;
        vis[typ] = 1;
        wupd_clsname.PB(sz);
        *((int*)(nmem+sz)) = typ;
        *((int*)(mem+C)) = sz+134217728;
        unsigned char* cstr = mem+C+4;
        sz+=4;
        for(auto ct:Tmap[typ][0]){
            nmem[sz] = cstr[ct];
            sz+=1;
        }
        debug(2);
        if(sz&1)sz+=1;
        for(auto ct:Tmap[typ][1]){
            nmem[sz] = cstr[ct];
            nmem[sz+1] = cstr[ct+1];
            sz+=2;
        }
        if(sz&3)sz+=1;
        if(sz&3)sz+=1;
        for(auto ct:Tmap[typ][2]){
            *((int*)(nmem+sz)) = *((int*)(cstr+ct));
            sz+=4;
        }
        debug(3);
        for(auto ct:Tmap[typ][3]){
        debug(ct);
            debug(*((int*)(cstr+ct)));
            int cv = *((int*)(cstr+ct)),cv2 = *((int*)(mem+cv));
            debug(cv);
            debug(cv2);
            debug(sz);
            if(cv == 1){
                *((int*)(nmem+sz)) = 1;
                sz+=4;
                continue;
            }
            if(cv2&134217728) *((int*)(nmem+sz)) = cv2-134217728;
            else{
                wupd_pointers.PB(sz);
                if(!(cv2&2048)){
                    *((int*)(mem+cv)) = cv2+2048;
                    Q.push(cv);
                }
                *((int*)(nmem+sz)) = cv;
            }
            sz+=4;
            debug(cv,"end");
        }
        debug(1235);
    }
    debug(234);
    for(auto ct:wupd_pointers){
        int cv = *((int*)(nmem+ct));
        int cv2 = *((int*)(mem+cv));
        if(cv2&134217728) *((int*)(nmem+ct)) = cv2-134217728;
    }
    debug(235);
    mem = opt;
    int Rn2 = *((int*)mem);
    for(int i=0;i<Rn2;i++){
      ((int*)mem)[i+1] = (*((int*)(old_heap+((int*)mem)[i+1])))-134217728;
    }
    
    debug(236);
    mem+=4*(Rn+1);
    int Tn2 = 0;
    for(int i=0;i<1024;i++){
        if(vis[i])rewire[i] = Tn2;
        Tn2+=vis[i];
    }
    *((int*)mem) = Tn2;
    mem+=4;
    debug(237);
    for(int i=0;i<Tn;i++){
        if(!vis[i])continue;
        int tnt = Tmap[i][0].size()+Tmap[i][1].size()+Tmap[i][2].size()+Tmap[i][3].size();
        *((int*)mem) = tnt;
        mem+=4;
        for(int j=0;j<Tmap[i][0].size();j++)mem[j] = 0;
        mem+=Tmap[i][0].size();
        for(int j=0;j<Tmap[i][1].size();j++)mem[j] = 1;
        mem+=Tmap[i][1].size();
        for(int j=0;j<Tmap[i][2].size();j++)mem[j] = 2;
        mem+=Tmap[i][2].size();
        for(int j=0;j<Tmap[i][3].size();j++)mem[j] = 3;
        mem+=Tmap[i][3].size();
    }
    debug(238);
    for(auto ct:wupd_clsname){
        *((int*)(nmem+ct)) = rewire[*((int*)(nmem+ct))];
    }
    *((int*)mem) = sz;
    memcpy(mem+4,nmem,sz);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注