Submission #1356137

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int N, M;
int x[101010];
int a[101010];
long long K;
struct dat
{
    int p1;
    int p2;
    int m;
};
vector<dat> poly;
dat pm(dat a, dat b, dat c)
{
    dat res; res.p1 = res.p2 = res.m = 0;
    
    multiset<int> pp;
    pp.insert(a.p1); pp.insert(a.p2);
    pp.insert(b.p1); pp.insert(b.p2);
    pp.insert(c.m);
    multiset<int>::iterator it;
    it = pp.find(a.m); if(it!=pp.end()) pp.erase(it); else res.m = a.m;
    it = pp.find(b.m); if(it!=pp.end()) pp.erase(it); else res.m = b.m;
    it = pp.find(c.p1); if(it!=pp.end()) pp.erase(it); else res.m = c.p1;
    it = pp.find(c.p2); if(it!=pp.end()) pp.erase(it); else res.m = c.p2;
    res.p1 = *pp.begin();
    if(pp.size()==2) res.p2 = *pp.rbegin();
    return res;
}
vector<dat> conv(vector<dat> a, vector<dat> b)
{
    vector<dat> res(N);
    for(int i=0; i<N; ++i)
        res[i] = pm(a[b[i].p1], a[b[i].p2], a[b[i].m]);
    return res;
}
vector<dat> pow(vector<dat> poly, long long x)
{
    if(x==1) return poly;
    vector<dat> ans = pow(poly, x/2);
    ans = conv(ans, ans);
    if(x%2==1) ans = conv(ans, poly);
    return ans;
}
int main()
{
    cin >> N;
    for(int i=0; i<N; ++i) cin >> x[i];
    cin >> M >> K;
    for(int i=0; i<M; ++i) cin >> a[i];
    for(int i=0; i<N; ++i)
    {
        dat a;
        a.p1 = 0; a.p2 = i; a.m = 0;
        poly.emplace_back(a);
    }
    for(int i=0; i<M; ++i)
        poly[a[i]-1] = pm(poly[a[i]], poly[a[i]-2], poly[a[i]-1]);
    vector<dat> res = pow(poly, K);
    for(int i=0; i<N; ++i)
    {
        //cout << res[i].p1 << res[i].p2 << res[i].m;
        cout << (long long)x[res[i].p1]+x[res[i].p2]-x[res[i].m] << ".0" << endl;
    }
    return 0;
}

Submission Info

Judge Result