Submission #1489973


Source Code Expand

Copy
/// c.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < decltype(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
# define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    fi>>n;
    static int p[1 << 20];
    static int q[1 << 20];
    for (int i = 1;i <= n;++i)
        fi>>p[i],q[p[i]] = i;
    static int D1[18][1 << 18];
    static int D2[18][1 << 18];
    for (int i = 1;i <= n;i += 2)
        D1[0][i] = i,D2[0][i] = -1;
    for (int i = 2;i <= n;i += 2)
        D2[0][i] = i,D1[0][i] = -1;
    auto Merge = [&](int a,int b)
    {
        if (min(a,b) == -1)
            return max(a,b);
        if (p[a] < p[b])
            return a;
        else
            return b;
    };
    for (int t = 1;t < 18;++t)
        for (int i = 1;i + (1 << t) <= n + 1;++i)
            D1[t][i] = Merge(D1[t - 1][i],D1[t - 1][i + (1 << (t - 1))]),
            D2[t][i] = Merge(D2[t - 1][i],D2[t - 1][i + (1 << (t - 1))]);
    static int Log[1 << 20];
    for (int i = 2;i <= n;++i)
        Log[i] = Log[i / 2] + 1;
    auto get1 = [&](int l,int r)
    {
        int k = Log[r - l + 1];
        return Merge(D1[k][l],D1[k][r - (1 << k) + 1]);
    };
    auto get2 = [&](int l,int r)
    {
        int k = Log[r - l + 1];
        return Merge(D2[k][l],D2[k][r - (1 << k) + 1]);
    };
    set < pair < int , pii > > ss;
    ss.insert(mp(p[get1(1,n)],mp(1,n)));
    vi ans;
    for (int cs = 0;2 * cs < n;++cs)
    {
        int pos = q[ss.begin()->x];
        int l = ss.begin()->y.x;
        int r = ss.begin()->y.y;
        ss.erase(ss.begin());
        if (l + 1 < pos)
        {
            if (l & 1)
                ss.insert(mp(p[get1(l,pos - 1)],mp(l,pos - 1)));
            else
                ss.insert(mp(p[get2(l,pos - 1)],mp(l,pos - 1)));
        }
        int nxt = -1;
        if (pos & 1)
            nxt = get2(pos,r);
        else
            nxt = get1(pos,r);
        ans.pb(p[pos]);
        ans.pb(p[nxt]);
        if (pos + 1 < nxt - 1)
        {
            if (pos & 1)
                ss.insert(mp(p[get2(pos + 1,nxt - 1)],mp(pos + 1,nxt - 1)));
            else
                ss.insert(mp(p[get1(pos + 1,nxt - 1)],mp(pos + 1,nxt - 1)));
        }
        if (nxt + 1 < r)
        {
            if (nxt & 1)
                ss.insert(mp(p[get2(nxt + 1,r)],mp(nxt + 1,r)));
            else
                ss.insert(mp(p[get1(nxt + 1,r)],mp(nxt + 1,r)));
        }
    }
    for (int i = 0;i < n;++i)
        fo << ans[i] << " \n"[i == n - 1];
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}

Submission Info

Submission Time
Task E - Young Maids
User reality
Language C++14 (GCC 5.4.1)
Score 800
Code Size 3710 Byte
Status
Exec Time 157 ms
Memory 46580 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt
All 800 / 800 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
Case Name Status Exec Time Memory
0_00.txt 3 ms 12544 KB
0_01.txt 3 ms 8448 KB
0_02.txt 3 ms 12544 KB
1_00.txt 3 ms 8448 KB
1_01.txt 3 ms 8448 KB
1_02.txt 124 ms 44148 KB
1_03.txt 124 ms 44276 KB
1_04.txt 124 ms 44148 KB
1_05.txt 154 ms 46196 KB
1_06.txt 156 ms 45812 KB
1_07.txt 155 ms 46580 KB
1_08.txt 152 ms 45812 KB
1_09.txt 125 ms 44148 KB
1_10.txt 126 ms 44148 KB
1_11.txt 126 ms 44148 KB
1_12.txt 149 ms 45812 KB
1_13.txt 154 ms 45940 KB
1_14.txt 153 ms 45940 KB
1_15.txt 157 ms 45940 KB
1_16.txt 154 ms 45940 KB
1_17.txt 155 ms 45940 KB
1_18.txt 153 ms 45940 KB
1_19.txt 153 ms 45940 KB