結果

問題 No.5002 stick xor
ユーザー ikdikd
提出日時 2018-05-28 21:42:23
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 2,303 bytes
コンパイル時間 2,850 ms
実行使用メモリ 1,440 KB
スコア 12,935
最終ジャッジ日時 2023-06-01 00:00:00
ジャッジサーバーID
（参考情報） 		judge7 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
1,436 KB
testcase_01 AC 3 ms
1,436 KB
testcase_02 AC 3 ms
1,436 KB
testcase_03 AC 3 ms
1,436 KB
testcase_04 AC 3 ms
1,440 KB
testcase_05 AC 3 ms
1,440 KB
testcase_06 AC 3 ms
1,436 KB
testcase_07 AC 3 ms
1,436 KB
testcase_08 AC 3 ms
1,436 KB
testcase_09 AC 3 ms
1,440 KB
testcase_10 AC 4 ms
1,440 KB
testcase_11 AC 3 ms
1,436 KB
testcase_12 AC 4 ms
1,440 KB
testcase_13 AC 3 ms
1,440 KB
testcase_14 AC 3 ms
1,436 KB
testcase_15 AC 3 ms
1,440 KB
testcase_16 AC 2 ms
1,440 KB
testcase_17 AC 4 ms
1,436 KB
testcase_18 AC 3 ms
1,436 KB
testcase_19 AC 4 ms
1,436 KB
testcase_20 AC 3 ms
1,440 KB
testcase_21 AC 3 ms
1,436 KB
testcase_22 AC 3 ms
1,436 KB
testcase_23 AC 4 ms
1,440 KB
testcase_24 AC 3 ms
1,440 KB
testcase_25 AC 4 ms
1,436 KB
testcase_26 AC 3 ms
1,436 KB
testcase_27 AC 3 ms
1,440 KB
testcase_28 AC 3 ms
1,436 KB
testcase_29 AC 4 ms
1,436 KB
testcase_30 AC 3 ms
1,440 KB
testcase_31 AC 4 ms
1,436 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Problem{
  import std.stdio, std.string, std.conv, std.algorithm;  
  import std.math, std.array, std.random;
  const int L_MAX=25;
  const int n=60, k=500;
  int[] li;
  int[][] a;
  this(int[] li, int[][] a){
    this.li=li.dup;
    this.a=a.dup;
  }

  auto idx=new int[][](30);
  void init(){
    foreach(int i, l; li){
      idx[l]~=i;
    }
  }

  int take(int l){
    int ret=-1;
    for(int i=l; i<=L_MAX; i++){
      if(idx[i].length>0){
        ret=idx[i].back;
        idx[i].popBack;
        break;
      }
    }
    return ret;
  }

  int take2(int l){
    int ret=-1;
    int[] cand;
    for(int i=l; i<=L_MAX; i++){
      if(idx[i].length>0){
        cand~=idx[i].back;
      }
    }
    if(cand.length>0){
      ret=cand.choice;
      idx[li[ret]].popBack;
    }
    return ret;
  }
  
  struct Rect{
    int a, b, c, d;
  }
  auto ans=new Rect[](k);
  void solve(){
    foreach(i; 0..n){
      int len=1;
      foreach(j; 0..(L_MAX))if(a[i][j]==1){
        int m=take2(len);
        if(m<0) goto hell;
        ans[m]=Rect(i, j, i, j+li[m]-1);
        foreach(l; j..(j+li[m])) a[i][l]^=1;
        len++;
      }
    }
    hell:;
  }

  void output(){
    int un_used=0;
    foreach(int i, l; li){
      auto r=ans[i];
      if(r.d-r.b>0){
        writeln(r.a+1, " ", r.b+1, " ", r.c+1, " ", r.d+1);
      }else{
        un_used++;
        writeln(n-1, " ", 1, " ", n-1, " ", l);
      }
    }
    // writeln(un_used);
  }

  void count(){
    int[int] cnt;
    foreach(i; 0..25){
      int c=0;
      foreach(j; 0..25){
        if(a[i][j]==1) c++;
        else{
          if(c in cnt) cnt[c]++;
          else cnt[c]=1;
          c=0;
        } 
      }
    }
    foreach(key; cnt.keys.sort){
      writeln(key, " ", cnt[key]);
    }
  }

  void show(){
  }
}

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n, k; rd(n, k);
  auto li=readln.split.to!(int[]);
  auto a=new int[][](n, n);
  foreach(i; 0..n){
    auto line=readln.chomp.to!(char[]);
    foreach(j; 0..n) a[i][j]=line[j]-'0';
  }

  auto problem=new Problem(li, a);
  problem.init;
  problem.solve;
  problem.output;

}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}
0