#859961 (JavaScript) No.2263 Perms

• 問題: No.2263 Perms
• ユーザー: kariya1975
• 提出日時: 2023-04-15 12:05:06
• 言語: JavaScript (node v21.7.1)
• 結果: TLE
• 実行時間: -
• コード長: 12,250 bytes
• コンパイル時間: 51 ms
• コンパイル使用メモリ: 6,688 KB
• 実行使用メモリ: 51,700 KB
• 最終ジャッジ日時: 2024-10-10 23:58:03
• 合計ジャッジ時間: 5,873 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	65 ms; 46,244 KB
testcase_01	AC	63 ms; 39,296 KB
testcase_02	AC	68 ms; 39,552 KB
testcase_03	AC	67 ms; 39,296 KB
testcase_04	AC	66 ms; 39,296 KB
testcase_05	AC	131 ms; 43,648 KB
testcase_06	TLE	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-

ソースコード

/// source code (in typescript)

// // @kariay1975/atcoder-tslib is a private package: 
// import {
//   Input,
//   InputStdin,
//   sortAsNumber,
//   sumNumber,
// } from '@kariya1975/atcoder-tslib';
// // use babel-plugin-macros for speed.
// import {
//   range,
//   arrayWith,
// } from '@kariya1975/atcoder-tslib/macro';
// 
// 
// type int = number;
// 
// const nextPerm = (xs: int[]): boolean => {
//   const swap = (i: int, j: int): void => {
//     const t = xs[i];
//     xs[i] = xs[j];
//     xs[j] = t;
//   };
//   for (const i of range(xs.length - 2, -1, -1)) {
//     if (xs[i] >= xs[i + 1]) continue;
//     for (const j of range(xs.length -1, -1, -1)) {
//       if (xs[j] <= xs[i]) continue;
//       swap(i, j);
//       for (const k of range(xs.length - i - 1)) {
//         const l = i + 1 + k;
//         const m = xs.length - 1 - k;
//         if (l > m) break;
//         swap(l, m);
//       } 
//       break;
//     }
//     return true;
//   }
//   return false;
// };
// 
// const gcd = (n: int, m: int): int => {
//   if (m === 0) return n;
//   return gcd(m, n % m);
// };
// 
// const gcds = (xs: int[]): int => {
//   const [x, ...rest] = xs;
//   if (rest.length === 0) return x;
//   return gcd(x, gcds(rest));
// };
// 
// const main = (input: Input, output: any[]): void => {
//   let [N, M] = input.getInts(2);
//   let g = M;
//   const A: int[][] = [];
//   for (const _ of range(N)) {
//     const a = input.getInts(N);
//     if (sumNumber(a) !== M) {
//       output.push(-1);
//       return;
//     }
//     A.push(a);
//     g = gcd(g, gcds(a));
//   }
// 
//   M /= g;
//   for (const a of A) {
//     for (let i of range(N)) {
//       a[i] /= g;
//     }
//   }
// 
//   const dfs = (i: int, perms: int[][]): int[][] | false => {
// // console.error(i, perms)
//     if (i === N) return perms;
//     const cs: int[] = [];
//     for (const j of range(N)) {
//       for (const _ of range(A[i][j])) cs.push(j);
//     }
//     let ps: int[][] = [];
//     for (const p of perms) {
//       ps.push([...p]);
//     }
//     const sets = arrayWith(M, (i) => new Set<int>(perms[i]));
//     do {
// // console.error(cs.join(' '))
//       let ok = true;
//       for (const j of range(M)) {
//         if (sets[j].has(cs[j])) {
//           ok = false;
//           break;
//         }
//         ps[j][i] = cs[j];
//       }
//       if (!ok) continue;
//       const result = dfs(i + 1, ps);
//       if (result !== false) return result; 
//     } while (nextPerm(cs));
//     return false;
//   };
// 
//   const result = dfs(0, arrayWith(M, () => []));
//   if (result === false) {
//     output.push(-1);
//   } else {
//     for (const p of result) {
//       const t = p.map(x => x + 1).join(' '); 
//       for (const _ of range(g)) {
//         output.push(t);
//       }
//     }
//   }
// };
// 
// const input = new InputStdin();
// input.setup().then(_ => {
//   const output = [];
//   main(input, output);
//   console.log(output.join('n'));
// });

// /// The code above transpiles as follows:
var C=Object.create;var b=Object.defineProperty;var R=Object.getOwnPropertyDescriptor;var j=Object.getOwnPropertyNames;var L=Object.getPrototypeOf,Q=Object.prototype.hasOwnProperty;var P=t=>b(t,"__esModule",{value:!0});var M=(t,e)=>()=>(e||t((e={exports:{}}).exports,e),e.exports);var G=(t,e,r)=>{if(e&&typeof e=="object"||typeof e=="function")for(let i of j(e))!Q.call(t,i)&&i!=="default"&&b(t,i,{get:()=>e[i],enumerable:!(r=R(e,i))||r.enumerable});return t},x=t=>G(P(b(t!=null?C(L(t)):{},"default",t&&t.__esModule&&"default"in t?{get:()=>t.default,enumerable:!0}:{value:t,enumerable:!0})),t);var N=M((ut,E)=>{"use strict";var U=function(t,e){return t<e};function h(t){if(!(this instanceof h))return new h(t);this.array=[],this.size=0,this.compare=t||U}h.prototype.clone=function(){var t=new h(this.compare);return t.size=this.size,t.array=this.array.slice(0,this.size),t};h.prototype.add=function(t){var e=this.size;this.array[this.size]=t,this.size+=1;for(var r,i;e>0&&(r=e-1>>1,i=this.array[r],!!this.compare(t,i));)this.array[e]=i,e=r;this.array[e]=t};h.prototype.heapify=function(t){this.array=t,this.size=t.length;var e;for(e=this.size>>1;e>=0;e--)this._percolateDown(e)};h.prototype._percolateUp=function(t,e){for(var r=this.array[t],i,s;t>0&&(i=t-1>>1,s=this.array[i],!(!e&&!this.compare(r,s)));)this.array[t]=s,t=i;this.array[t]=r};h.prototype._percolateDown=function(t){for(var e=this.size,r=this.size>>>1,i=this.array[t],s,n,o;t<r&&(s=(t<<1)+1,n=s+1,o=this.array[s],n<e&&this.compare(this.array[n],o)&&(s=n,o=this.array[n]),!!this.compare(o,i));)this.array[t]=o,t=s;this.array[t]=i};h.prototype._removeAt=function(t){if(!(t>this.size-1||t<0))return this._percolateUp(t,!0),this.poll()};h.prototype.remove=function(t){for(var e=0;e<this.size;e++)if(!this.compare(this.array[e],t)&&!this.compare(t,this.array[e]))return this._removeAt(e),!0;return!1};h.prototype.removeOne=function(t){if(typeof t=="function"){for(var e=0;e<this.size;e++)if(t(this.array[e]))return this._removeAt(e)}};h.prototype.removeMany=function(t,e){if(typeof t!="function"||this.size<1)return[];e=e?Math.min(e,this.size):this.size;for(var r=0,i=new Array(e),s=0,n=new Array(this.size);r<e&&!this.isEmpty();){var o=this.poll();t(o)?i[r++]=o:n[s++]=o}i.length=r;for(var u=0;u<s;)this.add(n[u++]);return i};h.prototype.peek=function(){if(this.size!=0)return this.array[0]};h.prototype.poll=function(){if(this.size!=0){var t=this.array[0];return this.size>1?(this.array[0]=this.array[--this.size],this._percolateDown(0)):this.size-=1,t}};h.prototype.replaceTop=function(t){if(this.size!=0){var e=this.array[0];return this.array[0]=t,this._percolateDown(0),e}};h.prototype.trim=function(){this.array=this.array.slice(0,this.size)};h.prototype.isEmpty=function(){return this.size===0};h.prototype.forEach=function(t){if(!(this.isEmpty()||typeof t!="function"))for(var e=0,r=this.clone();!r.isEmpty();)t(r.poll(),e++)};h.prototype.kSmallest=function(t){if(this.size==0)return[];t=Math.min(this.size,t);var e=new h(this.compare);let r=Math.min((t>0?Math.pow(2,t-1):0)+1,this.size);e.size=r,e.array=this.array.slice(0,r);for(var i=new Array(t),s=0;s<t;s++)i[s]=e.poll();return i};E.exports=h});var $=M((qt,D)=>{"use strict";function a(t){if(this._capacity=B(t),this._length=0,this._front=0,A(t)){for(var e=t.length,r=0;r<e;++r)this[r]=t[r];this._length=e}}a.prototype.toArray=function(){for(var e=this._length,r=new Array(e),i=this._front,s=this._capacity,n=0;n<e;++n)r[n]=this[i+n&s-1];return r};a.prototype.push=function(e){var r=arguments.length,i=this._length;if(r>1){var s=this._capacity;if(i+r>s){for(var o=0;o<r;++o){this._checkCapacity(i+1);var n=this._front+i&this._capacity-1;this[n]=arguments[o],i++,this._length=i}return i}else{for(var n=this._front,o=0;o<r;++o)this[n+i&s-1]=arguments[o],n++;return this._length=i+r,i+r}}if(r===0)return i;this._checkCapacity(i+1);var o=this._front+i&this._capacity-1;return this[o]=e,this._length=i+1,i+1};a.prototype.pop=function(){var e=this._length;if(e!==0){var r=this._front+e-1&this._capacity-1,i=this[r];return this[r]=void 0,this._length=e-1,i}};a.prototype.shift=function(){var e=this._length;if(e!==0){var r=this._front,i=this[r];return this[r]=void 0,this._front=r+1&this._capacity-1,this._length=e-1,i}};a.prototype.unshift=function(e){var r=this._length,i=arguments.length;if(i>1){var o=this._capacity;if(r+i>o){for(var u=i-1;u>=0;u--){this._checkCapacity(r+1);var o=this._capacity,s=(this._front-1&o-1^o)-o;this[s]=arguments[u],r++,this._length=r,this._front=s}return r}else{for(var n=this._front,u=i-1;u>=0;u--){var s=(n-1&o-1^o)-o;this[s]=arguments[u],n=s}return this._front=n,this._length=r+i,r+i}}if(i===0)return r;this._checkCapacity(r+1);var o=this._capacity,u=(this._front-1&o-1^o)-o;return this[u]=e,this._length=r+1,this._front=u,r+1};a.prototype.peekBack=function(){var e=this._length;if(e!==0){var r=this._front+e-1&this._capacity-1;return this[r]}};a.prototype.peekFront=function(){if(this._length!==0)return this[this._front]};a.prototype.get=function(e){var r=e;if(r===(r|0)){var i=this._length;if(r<0&&(r=r+i),!(r<0||r>=i))return this[this._front+r&this._capacity-1]}};a.prototype.isEmpty=function(){return this._length===0};a.prototype.clear=function(){for(var e=this._length,r=this._front,i=this._capacity,s=0;s<e;++s)this[r+s&i-1]=void 0;this._length=0,this._front=0};a.prototype.toString=function(){return this.toArray().toString()};a.prototype.valueOf=a.prototype.toString;a.prototype.removeFront=a.prototype.shift;a.prototype.removeBack=a.prototype.pop;a.prototype.insertFront=a.prototype.unshift;a.prototype.insertBack=a.prototype.push;a.prototype.enqueue=a.prototype.push;a.prototype.dequeue=a.prototype.shift;a.prototype.toJSON=a.prototype.toArray;Object.defineProperty(a.prototype,"length",{get:function(){return this._length},set:function(){throw new RangeError("")}});a.prototype._checkCapacity=function(e){this._capacity<e&&this._resizeTo(B(this._capacity*1.5+16))};a.prototype._resizeTo=function(e){var r=this._capacity;this._capacity=e;var i=this._front,s=this._length;if(i+s>r){var n=i+s&r-1;Y(this,0,this,r,n)}};var A=Array.isArray;function Y(t,e,r,i,s){for(var n=0;n<s;++n)r[n+i]=t[n+e],t[n+e]=void 0}function Z(t){return t=t>>>0,t=t-1,t=t|t>>1,t=t|t>>2,t=t|t>>4,t=t|t>>8,t=t|t>>16,t+1}function B(t){if(typeof t!="number")if(A(t))t=t.length;else return 16;return Z(Math.min(Math.max(16,t),1073741824))}D.exports=a});var y=x(require("fs"));var q=class{constructor(e){this.data=e!=null?e:"",this.index=0}isSpace(e){return e===" "||e===`
`}getString(){for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;let e=this.index;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)this.index++;let r=this.index;return this.data.slice(e,r)}getBigInt(){return BigInt(this.getString())}getInt(){return parseInt(this.getString())}getNumber(){return Number(this.getString())}getNumbers(e){let r=[];for(let i of _(e))r.push(this.getNumber());return r}getBigInts(e){let r=[];for(let i of _(e))r.push(this.getBigInt());return r}getInts(e){let r=[];for(let i of _(e))r.push(this.getInt());return r}getStrings(e){let r=[];for(let i of _(e))r.push(this.getString());return r}get(e){if(typeof e=="number")return this.getNumber();if(typeof e=="bigint")return this.getBigInt();if(typeof e=="string")return this.getString()}gets(e,r){if(typeof e=="number")return this.getNumbers(r);if(typeof e=="bigint")return this.getBigInts(r);if(typeof e=="string")return this.getStrings(r)}},z=class extends q{constructor(){super();(0,y.existsSync)("/dev/stdin")&&(super.data=(0,y.readFileSync)("/dev/stdin","utf-8"))}async setup(){if((0,y.existsSync)("/dev/stdin"))return;let e=[];for await(let s of process.stdin)e.push(s);let i=Buffer.concat(e).toString();super.data=i}};var X=x(N());var tt=x($());var m=(t,e)=>{let r=new Array(t);for(let i=0;i<t;++i)r[i]=e(i);return r};function*it(t){for(let e=0;e<t;++e)yield e}function*F(t,e,r=1){if(r>0)for(let i=t;i<e;i+=r)yield i;else if(r<0)for(let i=t;i>e;i+=r)yield i}var _=(t,e=null,r=null)=>e===null?it(t):r===null?F(t,e):F(t,e,r);var I=t=>{let e=0;for(let r of t)e+=r;return e};var st=t=>{let e=(r,i)=>{let s=t[r];t[r]=t[i],t[i]=s};for(let r=t.length-2,i=-1,s=-1;r>i;r+=s)if(!(t[r]>=t[r+1])){for(let n=t.length-1,o=-1,u=-1;n>o;n+=u)if(!(t[n]<=t[r])){e(r,n);for(let p=0,c=t.length-r-1;p<c;++p){let f=r+1+p,g=t.length-1-p;if(f>g)break;e(f,g)}break}return!0}return!1},S=(t,e)=>e===0?t:S(e,t%e),k=t=>{let[e,...r]=t;return r.length===0?e:S(e,k(r))},nt=(t,e)=>{let[r,i]=t.getInts(2),s=i,n=[];for(let p=0,c=r;p<c;++p){let f=t.getInts(r);if(I(f)!==i){e.push(-1);return}n.push(f),s=S(s,k(f))}i/=s;for(let p of n)for(let c=0,f=r;c<f;++c)p[c]/=s;let o=(p,c)=>{if(p===r)return c;let f=[];for(let l=0,v=r;l<v;++l)for(let d=0,w=n[p][l];d<w;++d)f.push(l);let g=[];for(let l of c)g.push([...l]);let W=m(i,l=>new Set(c[l]));do{let l=!0;for(let d=0,w=i;d<w;++d){if(W[d].has(f[d])){l=!1;break}g[d][p]=f[d]}if(!l)continue;let v=o(p+1,g);if(v!==!1)return v}while(st(f));return!1},u=o(0,m(i,()=>[]));if(u===!1)e.push(-1);else for(let p of u){let c=p.map(f=>f+1).join(" ");for(let f=0,g=s;f<g;++f)e.push(c)}},O=new z;O.setup().then(t=>{let e=[];nt(O,e),console.log(e.join(`
`))});