Submission #486224


Source Code Expand

Copy
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
	template<class S,class T>
	ostream &operator <<(ostream& out,const pair<S,T>& a){
		out<<'('<<a.fr<<','<<a.sc<<')';
		return out;
	}
}

const int INF=5e8;

int w,h;
vector<int> g[6000];

int ar[100005];

typedef vector<int> vi;
vector<vi> perm;

int dp[6000],dp2[6005];

int head[6000],last[6000],back[100005],type[100005];



int K;
void shift(int a){
  REP(i,K){
    vi p=perm[i];
    swap(p[a],p[a+1]);
    int cnt=lower_bound(ALL(perm),p)-perm.begin();
    dp2[i]=dp[cnt];
  }
  memcpy(dp,dp2,sizeof(dp));
}


int revN(vi a){
  int res=0;
  REP(i,w) REP(j,i) if(a[i]<a[j]) ++res;
  return res;
}


void bfs(){
  priority_queue<pi,vector<pi>,greater<pi> >pq;

  REP(i,K) dp2[i]=dp[i];
  REP(i,K) pq.push(mp(dp[i],i));
  while(!pq.empty()){
    pi cur=pq.top();pq.pop();
    for(auto to:g[cur.sc]){
      if(dp2[to]>cur.fr+1){
        dp2[to]=cur.fr+1;
        pq.push(mp(cur.fr+1,to));
      }
    }
  }
  memcpy(dp,dp2,sizeof(dp));
}

int main(){
  cin>>w>>h;

  if(h>100) return 0;
  K=1;
  REP(i,w) K*=i+1;

  vi trg(w);
  REP(i,h) scanf("%d",&ar[i]);
  REP(i,w) scanf("%d",&trg[i]);

  vi tmp(w);
  REP(i,w) tmp[i]=i;
  do{
    perm.pb(tmp);
  }while(next_permutation(ALL(tmp)));


  REP(i,K){
    vi p=perm[i];
    REP(j,w-1){
      vi q=p;
      swap(q[j],q[j+1]);
      int nxt=lower_bound(ALL(perm),q)-perm.begin();
      g[i].pb(nxt);
    }
  }


  vi cur(w);

  REP(i,K){
    dp[i]=revN(perm[i]);
  }


  REP(i,h){
    int a=ar[i];

    shift(a);

    bfs();
  }

  int trg_state=lower_bound(ALL(perm),trg)-perm.begin();
  printf("%d\n",dp[trg_state]);
	return 0;
}

Submission Info

Submission Time
Task C - 天下一不正
User hogloid
Language C++11 (GCC 4.9.2)
Score 45
Code Size 2494 Byte
Status
Exec Time 279 ms
Memory 1708 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,h) scanf("%d",&ar[i]);
                              ^
./Main.cpp:100:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,w) scanf("%d",&trg[i]);
                               ^

Judge Result

Set Name Score / Max Score Test Cases
small 45 / 45 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt
All 0 / 105 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt, 10_large100.txt, 10_large101.txt, 10_large102.txt, 10_large103.txt, 10_large104.txt, 10_large105.txt, 10_large106.txt, 10_large107.txt, 10_large108.txt, 10_large109.txt, 10_large110.txt, 10_large111.txt, 10_large112.txt, 10_large113.txt, 10_large114.txt, 10_large115.txt, 10_large116.txt, 10_large117.txt, 10_large118.txt, 10_large119.txt, 10_large120.txt, 10_large121.txt, 10_large122.txt, 10_large123.txt, 10_large124.txt, 10_large125.txt, 10_large126.txt, 10_large127.txt, 10_large128.txt, 10_large129.txt, 10_large130.txt, 10_large131.txt, 10_large132.txt, 10_large133.txt, 10_large134.txt, 10_large135.txt, 11_manual00.txt
Case Name Status Exec Time Memory
00_sample_1.txt 26 ms 924 KB
00_sample_2.txt 28 ms 860 KB
01_manual00.txt 26 ms 1052 KB
01_manual01.txt 26 ms 940 KB
01_manual02.txt 35 ms 1448 KB
01_manual03.txt 50 ms 1700 KB
01_manual04.txt 271 ms 1696 KB
05_small100.txt 25 ms 1048 KB
05_small101.txt 27 ms 1052 KB
05_small102.txt 28 ms 888 KB
05_small103.txt 30 ms 1052 KB
05_small104.txt 50 ms 1696 KB
05_small105.txt 27 ms 932 KB
05_small106.txt 28 ms 1052 KB
05_small107.txt 34 ms 936 KB
05_small108.txt 56 ms 1048 KB
05_small109.txt 274 ms 1708 KB
05_small110.txt 158 ms 1708 KB
05_small111.txt 68 ms 1576 KB
05_small112.txt 25 ms 1056 KB
05_small113.txt 27 ms 1056 KB
05_small114.txt 32 ms 936 KB
05_small115.txt 55 ms 1048 KB
05_small116.txt 274 ms 1696 KB
05_small117.txt 63 ms 1572 KB
05_small118.txt 92 ms 1692 KB
05_small119.txt 100 ms 1576 KB
05_small120.txt 181 ms 1700 KB
05_small121.txt 274 ms 1700 KB
05_small122.txt 272 ms 1700 KB
05_small123.txt 270 ms 1696 KB
05_small124.txt 270 ms 1700 KB
05_small125.txt 275 ms 1696 KB
05_small126.txt 275 ms 1684 KB
05_small127.txt 277 ms 1620 KB
05_small128.txt 279 ms 1700 KB
05_small129.txt 271 ms 1624 KB
05_small130.txt 269 ms 1624 KB
05_small131.txt 267 ms 1580 KB
05_small132.txt 279 ms 1624 KB
05_small133.txt 275 ms 1696 KB
05_small134.txt 276 ms 1700 KB
10_large100.txt 26 ms 924 KB
10_large101.txt 26 ms 928 KB
10_large102.txt 25 ms 932 KB
10_large103.txt 24 ms 1052 KB
10_large104.txt 26 ms 928 KB
10_large105.txt 26 ms 932 KB
10_large106.txt 25 ms 936 KB
10_large107.txt 25 ms 944 KB
10_large108.txt 24 ms 1048 KB
10_large109.txt 25 ms 1048 KB
10_large110.txt 27 ms 1044 KB
10_large111.txt 25 ms 1048 KB
10_large112.txt 25 ms 940 KB
10_large113.txt 26 ms 936 KB
10_large114.txt 25 ms 1056 KB
10_large115.txt 26 ms 852 KB
10_large116.txt 26 ms 924 KB
10_large117.txt 26 ms 928 KB
10_large118.txt 25 ms 936 KB
10_large119.txt 25 ms 924 KB
10_large120.txt 25 ms 928 KB
10_large121.txt 24 ms 1048 KB
10_large122.txt 25 ms 852 KB
10_large123.txt 26 ms 924 KB
10_large124.txt 25 ms 1044 KB
10_large125.txt 25 ms 1048 KB
10_large126.txt 25 ms 1048 KB
10_large127.txt 25 ms 928 KB
10_large128.txt 25 ms 1044 KB
10_large129.txt 25 ms 928 KB
10_large130.txt 24 ms 924 KB
10_large131.txt 26 ms 924 KB
10_large132.txt 26 ms 1052 KB
10_large133.txt 24 ms 1048 KB
10_large134.txt 27 ms 1044 KB
10_large135.txt 25 ms 936 KB
11_manual00.txt 25 ms 1048 KB