Hướng dẫn giải của Minimum Permutation
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
var i:longint; m,x,y,z,n:int64; begin repeat read(n,m); if n=-1 then halt; x:=trunc(sqrt(m*2))-10; if x<0 then x:=0; while x*(x-1)<m*2 do x:=x+1; y:=x*(x-1) div 2-m; z:=n-x; for i:=1 to z do write(i,' '); if y>0 then begin write(n-y,' '); for i:=n downto n-y+1 do write(i,' '); for i:=n-y-1 downto z+1 do write (i,' '); end else for i:=1 to x do write(n-i+1,' '); writeln; until false; end.
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 5; int bit[N], nxt[N]; int n, m; void update(int i) { for (; i <= n; i += i & -i) ++bit[i]; } int prefixSum(int i) { int ans = 0; for (; i; i -= i & -i) ans += bit[i]; return ans; } int getNext(int i) { if (nxt[i] < i) return nxt[i]; return nxt[i] = getNext(nxt[i] + (nxt[i] == i)); } void solve() { for (int i = 1; i <= n + 1; ++i) bit[i] = 0, nxt[i] = i - 1; int invCnt = 0; for (int i = 1; i <= n; ++i) { int maxBuff = (long long)(n - i) * (n - i - 1) / 2; int l = 1, r = n, v = 0; while (l <= r) { int mid = l + r >> 1; int pos = getNext(mid) + 1; if (pos > n) { r = mid - 1; continue; } int more = pos - 1 - prefixSum(pos); if (invCnt + maxBuff + more >= m) v = pos, r = mid - 1; else l = mid + 1; } cout << v << ' '; invCnt += v - 1 - prefixSum(v); update(v); nxt[v] = v; } cout << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); while (cin >> n >> m) { if (n == -1) break; solve(); } return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} uses math; const FINP=''; FOUT=''; MAXN=50111; var f1,f2:text; n:longint; m:int64; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure solve; var i,u,lh:longint; k:int64; begin k:=-1; for i:=n+1 downto 0 do begin k+=1; if k*(k-1)>>1>=m then break; end; if k*(k-1)>>1=m then begin for i:=1 to n-k do write(f2,i,' '); for i:=n downto n-k+1 do write(f2,i,' '); writeln(f2); exit; end; for i:=1 to n-k do write(f2,i,' '); u:=n-k+1; lh:=0; while lh+((k-2)*(k-1))>>1<m do begin inc(u); lh+=1; end; write(f2,u,' '); for i:=n downto n-k+1 do if i<>u then write(f2,i,' '); writeln(f2); end; begin openF; read(f1,n,m); while (n>=0) and (m>=0) do begin solve; read(f1,n,m); end; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int main() { long long n,m,a[50001]; while(scanf("%lld %lld",&n,&m)>0 && n>0) { int flag = 0; for(int i = n-1;i>=0;i--) { if(m>((long long)i*(i-1))/2) { flag = i; break; } } for(int i = 1;i<=n;i++) a[i] = i; if(m==0) flag = 0; else flag++; //printf("%d",flag); if(m!=0) { int u = n-flag+1; int v = m-(flag-1)*(flag-2)/2+u; int t = n+u-v; // printf(" %d %d\n",u,v); for(int i = u;i<=n;i++) a[i] = u+n-i; int x = a[t]; for(int i = t;i>u;i--) a[i] = a[i-1]; a[u] = x; } for(int i = 1;i<=n;i++) printf("%lld ",a[i]); printf("\n"); } // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program MMINPER; Const input = ''; output = ''; maxn = 50000; Var fi,fo: text; n: integer; m: int64; d: array[1..maxn] of int64; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure solve; Var i,j,del,val: int64; k: integer; Begin i:= 1; j:= n - 1; While m < int64(j * (j + 1) div 2) do Begin d[i]:= i; dec(j); inc(i); End; If m = int64(j * (j + 1) div 2) then For k:= i to n do d[k]:= (n + i) - k else Begin dec(i); del:= m - int64(j * (j + 1) div 2); d[i]:= i + del; val:= n; For k:= i + 1 to n do Begin If val <> d[i] then d[k]:= val else Begin dec(val); d[k]:= val; End; dec(val); End; End; For k:= 1 to n do write(fo, d[k], ' '); Writeln(fo); End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; Repeat Readln(fi, n, m); If n <> -1 then solve; Until n = -1; closefile; End.
Code mẫu của khuc_tuan
// {$APPTYPE CONSOLE} {$mode delphi} type Main = class b : array[0..50000] of boolean; sum : array[0..500] of integer; procedure solve(n, m : integer); procedure extract(x, n : integer); end; procedure Main.extract(x, n : integer); var j, k, i, c : integer; begin c := 0; for i:=0 to n div 100 do begin inc(c, sum[i]); if c >= x then begin k := x - (c - sum[i]); dec(sum[i]); for j:= i * 100 to n do if b[j] then begin dec(k); if k=0 then begin b[j] := false; write(j, #32); break; end; end; break; end; end; end; procedure Main.solve(n, m : integer); var need, can, i : integer; begin for i:=0 to 500 do if sum[i] <> 0 then writeln('ha ha'); for i:=1 to 500 do sum[i] := 0; for i:=1 to n do begin b[i] := true; inc(sum[i div 100]); end; for i:=n-1 downto 0 do begin can := int64(i) * (i-1) div 2; need := m - can; if need < 0 then need := 0; m := m - need; extract(need+1, n); end; writeln; end; var n, m : integer; solver : Main; begin while true do begin readln(n, m); if (n=-1) and (m=-1) then break; solver := Main.Create; solver.solve(n,m); solver.Free; end; end.
Bình luận