AtCoder Beginner Contest 013

Submission #6903342

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N,M,D;cin >> N >> M >> D;
  vector<int> v(N+1);
  int n_2 = 0;
  {
    int n = D;
    while(n){
      ++n_2;
      n/=2;
    }
  }

  vector<vector<int> > d(n_2,vector<int>(N+1));
  rep(i,N+1)v[i] = i;
  rep(i,M){
    int x;cin >> x;
    swap(v[x],v[x+1]);
  }

  repp(i,1,N+1) d[0][v[i]] = i;
  //repp(i,1,N+1) cout << d[0][i] SPF;
  //cout << endl;
  repp(n,1,n_2){
    repp(i,1,N+1) d[n][i] = d[n-1][d[n-1][i]];
    //repp(i,1,N+1) cout << d[n][i] SPF;
    //cout << endl;
  }

  int dp[2][N+1];
  int *pre,*nxt;
  pre = dp[0];
  nxt = dp[1];
  rep(i,N+1) pre[i] = i;
  rep(n,n_2){
    if(D>>n&1){
      repp(i,1,N+1) nxt[i] = d[n][pre[i]];
      swap(pre,nxt);
    }
  }
  swap(pre,nxt);
  repp(i,1,N+1) cout << nxt[i] << endl;
  return 0;
}

Submission

Task問題 D - 阿弥陀
User nameユーザ名 issei
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1950 Byte
File nameファイル名
Exec time実行時間 177 ms
Memory usageメモリ使用量 13816 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 10 / 10 sample_1.txt,01_i.txt,01_random01.txt,01_random02.txt,01_random03.txt,01_random04.txt,01_random05.txt,01_random06.txt,01_random07.txt
Subtask2 20 / 20 sample_1.txt,sample_2.txt,sample_3.txt,02_i.txt,02_p.txt,02_random01.txt,02_random02.txt,02_random03.txt,02_random04.txt,02_random05.txt,02_random06.txt,02_random07.txt,02_random08.txt,02_rp01.txt,02_rp02.txt,02_rp03.txt,02_rp04.txt,02_rp05.txt
Subtask3 20 / 20 sample_1.txt,sample_2.txt,03_i.txt,03_random01.txt,03_random02.txt,03_random03.txt,03_random04.txt,03_random05.txt,03_random06.txt,03_random07.txt,03_random08.txt,03_random09.txt,03_random10.txt,03_random11.txt,03_random12.txt,03_random13.txt,03_random14.txt,03_random15.txt
Subtask4 50 / 50 sample_1.txt,sample_2.txt,sample_3.txt,04_i.txt,04_p1.txt,04_p2.txt,04_random01.txt,04_random02.txt,04_random03.txt,04_random04.txt,04_random05.txt,04_random06.txt,04_random07.txt,04_random08.txt,04_random09.txt,04_random10.txt,04_random11.txt,04_random12.txt,04_random13.txt,04_rp01.txt,04_rp02.txt,04_rp03.txt,04_rp04.txt,04_rp05.txt,04_rp06.txt,04_rp07.txt,04_rp08.txt,04_rp09.txt,04_rp10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01_i.txt AC 167 ms 2424 KB
01_random01.txt AC 1 ms 256 KB
01_random02.txt AC 1 ms 256 KB
01_random03.txt AC 1 ms 256 KB
01_random04.txt AC 6 ms 384 KB
01_random05.txt AC 153 ms 2424 KB
01_random06.txt AC 167 ms 2424 KB
01_random07.txt AC 167 ms 2424 KB
02_i.txt AC 3 ms 256 KB
02_p.txt AC 3 ms 256 KB
02_random01.txt AC 1 ms 256 KB
02_random02.txt AC 1 ms 256 KB
02_random03.txt AC 3 ms 256 KB
02_random04.txt AC 3 ms 256 KB
02_random05.txt AC 4 ms 256 KB
02_random06.txt AC 9 ms 256 KB
02_random07.txt AC 16 ms 256 KB
02_random08.txt AC 16 ms 256 KB
02_rp01.txt AC 3 ms 256 KB
02_rp02.txt AC 3 ms 256 KB
02_rp03.txt AC 3 ms 256 KB
02_rp04.txt AC 3 ms 256 KB
02_rp05.txt AC 3 ms 384 KB
03_i.txt AC 1 ms 256 KB
03_random01.txt AC 2 ms 256 KB
03_random02.txt AC 12 ms 256 KB
03_random03.txt AC 10 ms 256 KB
03_random04.txt AC 10 ms 256 KB
03_random05.txt AC 3 ms 256 KB
03_random06.txt AC 3 ms 256 KB
03_random07.txt AC 4 ms 256 KB
03_random08.txt AC 1 ms 256 KB
03_random09.txt AC 4 ms 256 KB
03_random10.txt AC 7 ms 256 KB
03_random11.txt AC 11 ms 256 KB
03_random12.txt AC 12 ms 256 KB
03_random13.txt AC 9 ms 256 KB
03_random14.txt AC 8 ms 256 KB
03_random15.txt AC 4 ms 256 KB
04_i.txt AC 173 ms 13816 KB
04_p1.txt AC 166 ms 13432 KB
04_p2.txt AC 132 ms 10440 KB
04_random01.txt AC 97 ms 7720 KB
04_random02.txt AC 76 ms 6352 KB
04_random03.txt AC 25 ms 1664 KB
04_random04.txt AC 28 ms 1408 KB
04_random05.txt AC 34 ms 2176 KB
04_random06.txt AC 102 ms 8340 KB
04_random07.txt AC 73 ms 5108 KB
04_random08.txt AC 62 ms 3968 KB
04_random09.txt AC 43 ms 2560 KB
04_random10.txt AC 101 ms 8464 KB
04_random11.txt AC 174 ms 13048 KB
04_random12.txt AC 174 ms 13432 KB
04_random13.txt AC 174 ms 12152 KB
04_rp01.txt AC 177 ms 12920 KB
04_rp02.txt AC 170 ms 13048 KB
04_rp03.txt AC 168 ms 13816 KB
04_rp04.txt AC 168 ms 12920 KB
04_rp05.txt AC 171 ms 12536 KB
04_rp06.txt AC 170 ms 12536 KB
04_rp07.txt AC 165 ms 12536 KB
04_rp08.txt AC 168 ms 12920 KB
04_rp09.txt AC 167 ms 13816 KB
04_rp10.txt AC 168 ms 13816 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB