比赛 2024暑假C班集训E 评测结果 AAAAAAAAAA
题目名称 Swapity Swapity Swap 最终得分 100
用户昵称 liuyiche 运行时间 0.195 s
代码语言 C++ 内存使用 9.44 MiB
提交时间 2024-07-14 09:51:10
显示代码纯文本
#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

int n, mx, k; 
vector<int> v(100005);
vector<int> vv(100005);
vector<int> last(100005);

struct node
{
    vector<int> d;
};
vector<node> m(32);
    
int main()
{
    freopen("usaco_Feb_swap.in", "r", stdin);
    freopen("usaco_Feb_swap.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> mx >> k;
    for(int i = 1; i <= n; ++i)
        v[i] = i;
    for(int i = 1; i <= mx; ++i)
    {
        int l, r;
        cin >> l >> r;
        reverse(v.begin()+l,v.begin()+r+1);
    }
    m[0].d = v; 
    int cnt = 1;
    for(int i = 1; i <= 30; ++i)
        m[i].d.resize(n+1);
    for(int i = 1; i <= 30; ++i)
        for(int j = 1; j <= n; ++j)
            m[i].d[j] = m[i-1].d[m[i-1].d[j]];
    last = v;
    vv = v;
    for(int mm = 30; mm >= 0; --mm)
        if(cnt+(1<<mm) <= k)
        {
            cnt += (1<<mm);
            for(int i = 1; i <= n; ++i)
                vv[i] = last[m[mm].d[i]];
            last = vv;
        }
    
    
    for(int i = 1; i <= n; ++i)
        cout << vv[i] << '\n';
    
   	return 0;
}