阿祁的部落格

Atcoder Beginner Contest 253 G - Swap Many Time 解題心得( 題目 )

解題概念:壓縮、規律

解題方法:本題顯然不可直接做，但是可以發現如果從(X,X+1)做到(X,N)，其實就剛好是把最後一個元素往前移到最前面，其它後移，所以可以先剛開始那一輪暴力，中間過程壓縮，最後繼續暴力，複雜度O(N)。

//Author:En Chi Tsung(欉恩祁)

//Date:2022/06/08

import java.util.*;

import java.time.*;

import java.io.*;

import java.math.*;

public class Main {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static long ret;

    public static int reti,rd,fx,fy,sx,sy;

    public static int[] A=new int[200005];

    public static int[] B=new int[200005];

    public static final int mod=998244353;

    public static final int G=3;

    public static boolean neg;

    public static void main(String[] args) throws Exception{

        final int n=readint();

        final long l=readlong();

        final long r=readlong();

        long idx=1;

        int L=1;

        int R=n-1;

        int li=0;

        for(int i=1;i<=n;i++) {

            A[i]=i;

        }

        while(idx+R<=l) {

            idx+=R;

            R--;

            L++;

        }

        li=L+1;

        for(;idx<l;idx++) {

            li++;

        }

        int tmp;

        for(;li<=n&&idx<=r;li++,idx++) {

            tmp=A[L];

            A[L]=A[li];

            A[li]=tmp;

        }

        

        if(idx>=r) {

            for(int i=1;i<=n;i++) {

                bw.write(A[i]+" ");

            }

            bw.flush();

            System.exit(0);

        }

        int cnt=0;

        final int la=L+1;

        L++;

        R--;

        while(idx+R<=r) {

            idx+=R;

            R--;

            cnt++;

            L++;

        }

 

        for(int i=1;i<=n;i++) {

            B[i]=A[i];

        }

        for(int i=n,j=la,k=0;k<cnt;i--,j++,k++) {

            B[j]=A[i];

        }

 

        for(int i=la+cnt;i<=n;i++) {

            B[i]=A[i-cnt];

        }

        for(int i=L+1;idx<=r;i++,idx++) {

            tmp=B[L];

            B[L]=B[i];

            B[i]=tmp;

        }

        

        for(int i=1;i<=n;i++) {

            bw.write(B[i]+" ");


        }

        bw.flush();

    }

 

    public static int readint() throws Exception{


        reti=0;

        neg=false;

        while(rd<48||rd>57) {

            rd=br.read();

            if(rd=='-') {

                neg=true;

            }

        }

        while(rd>47&&rd<58) {

            reti*=10;

            reti+=(rd&15);

            rd=br.read();

        }

        if(neg)reti*=-1;

        return reti;

    }

    

    public static long readlong() throws Exception{

        ret=0;

        neg=false;

        while(rd<48||rd>57) {

            rd=br.read();

            if(rd=='-') {

                neg=true;

            }

        }

        while(rd>47&&rd<58) {

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        if(neg)ret*=-1;

        return ret;

    }

}