เครื่องเคลื่อนย้ายมวลสาร: ท่าโลภที่ตอบตัวอย่างถูกทั้งสองชุด แล้วยังผิดอยู่ดี

#include <bits/stdc++.h>
using namespace std;
int LIM;
int simulate(vector<pair<int,int>>& ps){
    static int par[400]; for(int i=0;i<=LIM;i++) par[i]=-1;
    for(auto&[a,b]:ps){ par[a]=b; par[b]=a; }
    int pos=0,sc=0;
    while(true){
        int nx=-1; for(int p=pos+1;p<=LIM;p++) if(par[p]>=0){ nx=p; break; }
        if(nx<0) return sc;
        pos=par[nx]; sc++; if(sc>3000) return -1;
    }
}
int main(int argc,char**argv){
    int n,m; scanf("%d %d %d",&n,&m,&LIM);
    vector<pair<int,int>> base(n);
    set<int> used;
    for(auto&p:base){ scanf("%d %d",&p.first,&p.second); used.insert(p.first); used.insert(p.second); }
    vector<int> freeP; for(int i=1;i<=LIM;i++) if(!used.count(i)) freeP.push_back(i);
    int F=(int)freeP.size(), need=2*m, best=0;
    vector<int> idx(need);
    function<void(int,int)> choose=[&](int start,int k){
        if(k==need){
            vector<int> sel; for(int i=0;i<need;i++) sel.push_back(freeP[idx[i]]);
            sort(sel.begin(),sel.end());
            do{
                vector<pair<int,int>> ps=base;
                for(int i=0;i<m;i++){ int a=sel[2*i],b=sel[2*i+1]; if(a>b) swap(a,b); ps.push_back({a,b}); }
                best=max(best,simulate(ps));
            } while(next_permutation(sel.begin(),sel.end()));
            return;
        }
        for(int i=start;i<F;i++){ idx[k]=i; choose(i+1,k+1); }
    };
    if(m==0) best=simulate(base); else choose(0,0);
    printf("%d\n",best);
}

#include <bits/stdc++.h>
using namespace std;
// อ่านเลขเองทีละไบต์ อินพุตมีสองล้านตัวเลข scanf ช้าเกินไปสำหรับลิมิตหนึ่งวินาที
static char ibuf[1<<25]; static size_t ipos=0, ilen=0;
static inline int rd(){
    while(ipos<ilen && (ibuf[ipos]<'0'||ibuf[ipos]>'9')) ipos++;
    int v=0; while(ipos<ilen && ibuf[ipos]>='0' && ibuf[ipos]<='9') v=v*10+(ibuf[ipos++]-'0');
    return v;
}
int main(){
    ilen=fread(ibuf,1,sizeof(ibuf),stdin);
    int n=rd(), m=rd();
    vector<int> W(n),E(n); int hi=0;
    for(int i=0;i<n;i++){ W[i]=rd(); E[i]=rd(); hi=max(hi,E[i]); }
    const int LIM=hi+2;                            // ใช้แค่ถึงปลายที่ไกลสุด ตำแหน่งจุดจบไม่มีผลกับคำตอบ
    vector<int> partnerAt(LIM,-1);                 // partnerAt[p] = ตำแหน่งปลายอีกข้าง
    for(int i=0;i<n;i++){ partnerAt[W[i]]=E[i]; partnerAt[E[i]]=W[i]; }
    // เรียงตำแหน่งปลายทั้งหมด แล้วให้เลข 1..2n  ช่วง I_j อยู่ทางตะวันออกของปลายที่ j (I_0 คือจากจุดเริ่ม)
    vector<int> pts; pts.reserve(2*n);
    for(int i=0;i<n;i++){ pts.push_back(W[i]); pts.push_back(E[i]); }
    sort(pts.begin(),pts.end());
    int P=(int)pts.size();
    vector<int> id(LIM,0);
    for(int i=0;i<P;i++) id[pts[i]]=i+1;           // ปลายตัวที่ i+1
    // nxt[j] = ช่วงถัดไปหลังจากเดินจบช่วง j   (j = 0..P-1)
    vector<int> nxt(P+1,-1);
    for(int j=0;j<P;j++) nxt[j]=id[ partnerAt[ pts[j] ] ];
    // เดินจาก I_0 ไปจนถึง I_P นับจำนวนช่วง
    vector<char> vis(P+1,0);
    long long base=0; int cur=0;
    while(cur!=P){ vis[cur]=1; cur=nxt[cur]; base++; }
    vis[P]=1;
    // วงที่เหลือ
    vector<long long> cyc;
    for(int j=0;j<P;j++) if(!vis[j]){ long long len=0; int u=j; while(!vis[u]){ vis[u]=1; u=nxt[u]; len++; } cyc.push_back(len); }
    sort(cyc.rbegin(),cyc.rend());
    long long ans=base;                            // base = จำนวนครั้งที่ถูกย้ายก่อนเพิ่มเครื่อง
    int used=0;
    for(size_t i=0;i<cyc.size() && used<m; i++,used++) ans+=cyc[i]+2;   // ดูดวงเข้ามาต่อในเส้นทาง
    long long r=m-used;                            // เครื่องที่เหลือเมื่อไม่มีวงให้ดูดแล้ว
    ans += (r/2)*4 + (r%2)*1;                      // ต้องเสียหนึ่งเครื่องแตกวงก่อน อีกเครื่องค่อยดูดกลับ
    printf("%lld\n",ans);
}

long long r = m - used;                  // เครื่องที่เหลือ ตอนไม่มีวงให้ดูดแล้ว
ans += r * 2;                            // <-- บรรทัดที่ผิด เดาว่าเครื่องละ 2 ด้วยความสมมาตร
                                         // ของจริงคือ (r / 2) * 4 + (r % 2) * 1

1
2
1 2