Overview
| SHA1 Hash: | 23dfcca431147302414b2a7e5dfdac6f175dd1e0 |
|---|---|
| Date: | 2011-02-23 11:18:09 |
| User: | kinaba |
| Comment: | renamed _lib to lib |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Deleted _lib/dataStructure/fenwickTree.cpp version [5a7c5bc1ec0fdf30]
1 //------------------------------------------------------------- < 2 // Fenwick Tree < 3 // O(log N) per each operation < 4 // < 5 // Verified by < 6 // - SRM424 Div1 LV3 < 7 //------------------------------------------------------------- < 8 < 9 template<typename T = LL> < 10 struct FenwickTree < 11 { < 12 vector<T> x; < 13 FenwickTree(size_t n, const T& v = T()) : x(n, v) {} < 14 < 15 void incr( int k, const T& a ) { // z[k] += a; < 16 for(; k < x.size(); k|=k+1) < 17 x[k] += a; < 18 } < 19 < 20 T sum(int i, int j) { // z[i]+...+z[j] : inclusive < 21 if(i) < 22 return sum(0, j) - sum(0, i-1); < 23 else { < 24 T v = T(); < 25 for(; j>=0; j=(j&(j+1))-1) < 26 v += x[j]; < 27 return v; < 28 } < 29 } < 30 }; <
Deleted _lib/dataStructure/rmq.cpp version [a0dd84df47a73891]
1 //------------------------------------------------------------- < 2 // Range Minimum Query < 3 // O(N log N) construction < 4 // O(1) per each query < 5 // returns the LEFTMOST/ALL minimum index (I hope) < 6 // < 7 // Verified by < 8 // - SRM337 Div1 LV2 < 9 // - SRM431 Div1 LV3 < 10 //------------------------------------------------------------- < 11 < 12 template<typename T> < 13 struct RMQ < 14 { < 15 vector< vector<int> > rm; < 16 vector<T> d; < 17 < 18 RMQ( const vector<T>& d ) : d(d) { < 19 int n = d.size(); < 20 < 21 // rm[k][x] = i s.t. d[i] is the minimum in [x, x+2^k) < 22 rm.push_back( vector<int>(n) ); < 23 for(int x=0; x<n; ++x) < 24 rm[0][x] = x; < 25 for(int k=1; (1<<k)<=n; ++k) { < 26 rm.push_back( rm[k-1] ); < 27 for(int x=0; x+(1<<k-1)<n; ++x) < 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) < 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; < 30 } < 31 } < 32 < 33 int operator()(int L, int R) const { // inclusive < 34 int k=0; < 35 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} < 36 LL i = rm[k][L]; < 37 LL j = rm[k][R-(1<<k)+1]; < 38 return (d[i]<=d[j] ? i : j); < 39 } < 40 < 41 vector<int> all(int L, int R) const { < 42 vector<int> ans; < 43 int minValue = d[(*this)(L, R)]; < 44 while( L <= R ) { < 45 int C = (*this)(L, R); < 46 if( minValue < d[C] ) < 47 break; < 48 ans.push_back(C); < 49 L = C+1; < 50 } < 51 return ans; < 52 } < 53 }; <
Deleted _lib/doc/hitori-sharp.pdf version [7c589d0ad4748936]
cannot compute difference between binary files
Deleted _lib/doc/lb_ub.txt version [6993ff5a52ea6cbc]
1 lb = lower_bound(k) < 2 ... k-1] lb [k ... < 3 < 4 < 5 ub = upper_bound(k) < 6 .., k] ub [k+1 ... < 7 < 8 < 9 なので任意の開閉区間をイテレータの [) 区間に直すには < 10 < 11 [A, B] < 12 = [ lower_bound(A), upper_bound(B) ) < 13 < 14 [A, B) < 15 = [ lower_bound(A), lower_bound(B) ) < 16 < 17 (A, B] < 18 = [ upper_bound(A), upper_bound(B) ) < 19 < 20 (A, B) < 21 = [ upper_bound(A), lower_bound(B) ) <
Deleted _lib/doc/nim.txt version [d63874d4c871cfe6]
1 // SRM338 Div1 LV3 < 2 < 3 定理のステートメント < 4 < 5 対象となるゲーム < 6 - 二人ゲーム < 7 - 二人とも動かせる手の集合は同じ < 8 - 動かせなくなった方が負け < 9 - 無限ループしない < 10 < 11 nim < 12 - サイズ s1, s2, .., sk の山がある < 13 - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除る < 14 - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け） < 15 < 16 *n をサイズ n の山が1個だけの nim とする < 17 - *0 は負け < 18 - *n は勝ち n>=1 < 19 < 20 ゲーム < 21 - 状態 G から打てる手で遷移する先を G1, ..., Gk とする < 22 G = {G1, ..., Gk} と書く < 23 < 24 等価 < 25 - 二つのゲームG, Fが等価なことを G ≡ F と書く < 26 等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること < 27 *n と *n は同サイズの山2つのnimは必敗なので等価。同イズでなければ必勝なので等価でない < 28 < 29 定理 < 30 - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk) < 31 where mex(S) = min(nat \setminus S) < 32 帰納的に、全てのゲームはなんらかの *n と等価 < 33 < 34 < 35 おまけ < 36 @G を G のnim値とする。つまりG≡*@G < 37 G = X + Y ならば @G = @X xor @Y < 38 山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいの同じ原理。 <
Deleted _lib/gcj/!gcj-smpl.aml version [9caa644d5228a4f9]
1 (**************************************************************************** < 2 * Written in < 3 * Alice 1.4 < 4 * http://www.ps.uni-saarland.de/alice/ < 5 ****************************************************************************) < 6 < 7 fun solve (n : int, k : int) : bool = < 8 let < 9 open Word < 10 infix 5 << andb < 11 val mask = (0wx1 << fromInt n) - 0wx1 < 12 in < 13 (fromInt k) andb mask = mask < 14 end < 15 < 16 fun main () = < 17 let < 18 fun readLine () = < 19 case TextIO.inputLine TextIO.stdIn of < 20 | NONE => [] < 21 | SOME(s) => map Int.fromString (String.tokens (fn x => < 22 < 23 fun parseOne c = < 24 case readLine() of < 25 | [SOME n, SOME k] => (c, (n, k)) < 26 | _ => assert false < 27 < 28 fun spawn solveOne (c, inp) = < 29 (c, solve inp) < 30 < 31 fun printOne (c, ans) = < 32 print ("Case #" ^ Int.toString (c+1) ^ ": " ^ (if ans th < 33 in < 34 case readLine () of < 35 | [SOME t] => List.app printOne (List.map solveOne (List.tabulat < 36 | _ => assert false < 37 end < 38 < 39 do main () < 40 do OS.Process.exit 0 <
Deleted _lib/gcj/!gcj-smpl.as version [a762a8ed088b0770]
1 ///////////////////////////////////////////////////////////////////////////// < 2 // Written in < 3 // ActionScript (using mtasc 1.14) < 4 // http://www.mtasc.org/ < 5 ///////////////////////////////////////////////////////////////////////////// < 6 < 7 class A < 8 { < 9 static function main(mc) < 10 { < 11 var input_string = "<paste the input data here>"; < 12 var input = input_string.split("\n"); < 13 var T = Number(input[0]); < 14 < 15 var output_string = "" < 16 for(var C=1; C<=T; ++C) < 17 { < 18 var theCase = input[C].split(" "); < 19 var N = Number(theCase[0]); < 20 var K = Number(theCase[1]); < 21 output_string += "Case #" + C + ": " + (solve(N,K)?"ON": < 22 } < 23 < 24 _root.createTextField("tf",0,0,0,800,600); < 25 _root.tf.text = output_string; < 26 } < 27 < 28 static function solve(N, K) < 29 { < 30 var mask = (1<<N) - 1; < 31 return (K & mask) == mask; < 32 } < 33 } <
Deleted _lib/gcj/!gcj-smpl.bl version [e21b6366bf8728d9]
1 ############################################################################# < 2 # Written in < 3 # Blue 1.7.5 < 4 # http://www.lechak.info/blue/ < 5 ############################################################################# < 6 < 7 global FROM_STRING = func { < 8 arg s; < 9 < 10 a = []; < 11 i = 0; < 12 loop { < 13 a = a.append( s.substr(i,i+1).num() ); < 14 (i=i+1) >= s.length() ? return; < 15 }; < 16 return a; < 17 }; < 18 < 19 global TO_STRING = func { < 20 arg x; < 21 lexical s = ""; < 22 x.map( func{ s = s + this; } ); < 23 return s; < 24 }; < 25 < 26 global LESS = func { < 27 arg x; < 28 arg y; < 29 < 30 xl = x.length(); < 31 yl = y.length(); < 32 (xl < yl) ? return 1; < 33 (xl > yl) ? return 0; < 34 i = 0; < 35 return loop { < 36 (i == xl) ? return 0; < 37 (x[i] < y[i]) ? return 1; < 38 (x[i] > y[i]) ? return 0; < 39 i = i+1; < 40 }; < 41 }; < 42 < 43 global SUB = func { < 44 arg x; < 45 arg y; < 46 < 47 x.length() > y.length() ? (y = [].resize(x.length()-y.length(),0).merge( < 48 z = [].resize(x.length(), 0); < 49 i = x.length()-1; < 50 carry = 0; < 51 loop { < 52 z[i] = x[i] - y[i] - carry; < 53 carry = z[i] < 0 ? (z[i]=z[i]+10; 1) : 0; < 54 (i=i-1) < 0 ? return; < 55 }; < 56 head = 0; < 57 loop { < 58 head == z.length()-1 ? return; < 59 z[head] != 0 ? return; < 60 head = head + 1; < 61 }; < 62 return z.slice(head, z.length()); < 63 }; < 64 < 65 global DBL = func { < 66 arg x; < 67 < 68 z = [].resize(x.length(), 0); < 69 i = x.length()-1; < 70 carry = 0; < 71 loop { < 72 z[i] = x[i] + x[i] + carry; < 73 carry = z[i] > 9 ? (z[i]=z[i]-10; 1) : 0; < 74 ((i=i-1) < 0) ? return; < 75 }; < 76 return (carry==1 ? [1].merge(z) : z); < 77 }; < 78 < 79 global DIF = func { < 80 arg x; < 81 arg y; < 82 return LESS(x, y) ? SUB(y, x) : SUB(x, y); < 83 }; < 84 < 85 global MOD = func { < 86 arg x; < 87 arg y; < 88 < 89 LESS(x,y) ? return x; < 90 z = MOD(x, DBL(y)); < 91 LESS(z,y) ? return z; < 92 return SUB(z,y); < 93 }; < 94 < 95 global ISZERO = func { < 96 arg x; < 97 return x[0] == 0; < 98 }; < 99 < 100 global GCD = func { < 101 arg x; < 102 arg y; < 103 return ISZERO(x) ? y : GCD(MOD(y,x),x); < 104 }; < 105 < 106 ############################################################################# < 107 < 108 solve = func { < 109 arg N; < 110 arg t; < 111 t = t.map( func{return FROM_STRING(this);} ); < 112 < 113 lexical t0 = t[0]; < 114 lexical g = DIF(t0, t[1]); < 115 t.slice(2, t.length()).map(func{ < 116 g = GCD(g, DIF(t0, this)); < 117 }); < 118 r = MOD(t[0], g); < 119 return TO_STRING( ISZERO(r) ? r : DIF(g,r) ); < 120 }; < 121 < 122 input = sys.library("streams").stdio().read(1000000000).split("\n").map(func{ret < 123 C = input[0][0].num(); < 124 < 125 CaseID = (args.length() >= 2 ? args[1].num() : 1); < 126 loop { < 127 "Case #".print(); < 128 CaseID.print(); < 129 ": ".print(); < 130 solve( input[CaseID][0].num(), input[CaseID].slice(1,input[CaseID].lengt < 131 "\n".print(); < 132 ((CaseID = CaseID+1) > C) ? return; < 133 }; <
Deleted _lib/gcj/!gcj-smpl.cl version [5615f7e126fc9cd7]
1 ///////////////////////////////////////////////////////////////////////////// < 2 // Writte in < 3 // Claire v3.3.37 < 4 // http://www.claire-language.com/ < 5 ///////////////////////////////////////////////////////////////////////////// < 6 < 7 D :: 1000000000 < 8 < 9 long <: ephemeral_object(hi:integer, lo:integer) < 10 < 11 [long!(x: integer) : long -> < 12 long(hi = x / D, lo = x mod D) < 13 ] < 14 < 15 [+(x:long, y:long) : long -> < 16 let lolo := x.lo - D + y.lo in < 17 ( < 18 if ( lolo < 0 ) < 19 long(hi = x.hi + y.hi, lo = lolo + D) < 20 else < 21 long(hi = x.hi + y.hi + 1, lo = lolo) < 22 ) < 23 ] < 24 < 25 [-(x:long, y:long) : long -> < 26 let lolo := x.lo - y.lo in < 27 ( < 28 if ( lolo < 0 ) < 29 long(hi = x.hi - y.hi - 1, lo = lolo + D) < 30 else < 31 long(hi = x.hi - y.hi, lo = lolo) < 32 ) < 33 ] < 34 < 35 [*(x:long, y:integer) : long -> < 36 let r := long!(0) in < 37 let c := x in < 38 (while (y > 0) ( < 39 (if (y mod 2 = 1) r :+ c), < 40 c := c + c, < 41 y :/ 2 < 42 ), < 43 r) < 44 ] < 45 < 46 [+(x:long, y:integer) : long -> < 47 x + long!(y) < 48 ] < 49 < 50 [<(x:long, y:long) : boolean -> < 51 if (x.hi < y.hi) < 52 true < 53 else if (x.hi > y.hi) < 54 false < 55 else < 56 x.lo < y.lo < 57 ] < 58 [>=(x:long, y:long) : boolean -> not(x < y)] < 59 [<=(x:long, y:long) : boolean -> not(y < x)] < 60 [>(x:long, y:long) : boolean -> (y < x)] < 61 < 62 [>=(x:long, y:integer) : boolean -> not(x < long!(y))] < 63 [<=(x:long, y:integer) : boolean -> not(long!(y) < x)] < 64 [<(x:long, y:integer) : boolean -> (x < long!(y))] < 65 [>(x:long, y:integer) : boolean -> (long!(y) < x)] < 66 < 67 [>=(x:integer, y:long) : boolean -> not(long!(x) < y)] < 68 [<=(x:integer, y:long) : boolean -> not(y < long!(x))] < 69 [<(x:integer, y:long) : boolean -> (long!(x) < y)] < 70 [>(x:integer, y:long) : boolean -> (y < long!(x))] < 71 < 72 < 73 [string!(x: long) : string -> < 74 if (x.hi > 0) < 75 let los := string!(x.lo) in < 76 string!(x.hi) /+ make_string(9 - length(los), '0') /+ lo < 77 else < 78 string!(x.lo) < 79 ] < 80 < 81 ///////////////////////////////////////////////////////////////////////////// < 82 < 83 [readLine() : list<integer> -> < 84 list<integer>{integer!(s) | s in explode(freadline(stdin), " ")} < 85 ] < 86 < 87 [solve(R:integer, k:integer, N:integer, g:list<integer>) -> < 88 let dest := make_list(N, 0) in < 89 let earn := make_list(N, long!(0)) in < 90 ( < 91 for s in (0 .. N - 1) ( < 92 let ride := long!(0) in < 93 let i := 0 in < 94 ( < 95 while (i < N) < 96 ( < 97 let ride2 := ride + g[((s + i) mod N) + < 98 (if (ride2 > k) < 99 break() < 100 else < 101 (ride := ride2, i :+ 1)) < 102 ), < 103 earn[s + 1] := ride, < 104 dest[s + 1] := ((s + i) mod N) + 1 < 105 ) < 106 ), < 107 let firstVisitTime := make_list(N, -1) in < 108 let firstVisitEarn := make_list(N, long!(0)) in < 109 let q := 1 in < 110 let totalEarn := long!(0) in < 111 let i := 0 in < 112 ( < 113 (while (i < R) ( < 114 if (firstVisitTime[q] = -1) < 115 ( < 116 firstVisitTime[q] := i, < 117 firstVisitEarn[q] := totalEarn, < 118 totalEarn :+ earn[q], < 119 q := dest[q], < 120 i :+ 1 < 121 ) < 122 else < 123 ( < 124 let loopSize := i - firstVisitTime[q] in < 125 let loopEarn := totalEarn - firstVisitEa < 126 let rest := R - i in < 127 ( < 128 totalEarn :+ loopEarn * (rest / < 129 // clear < 130 firstVisitTime := make_list(N, - < 131 i := R - (rest mod < 132 ) < 133 ) < 134 )), < 135 princ(string!(totalEarn)) < 136 ) < 137 ) < 138 ] < 139 < 140 [main() -> < 141 let T := readLine()[1] in < 142 for C in (1 .. T) < 143 ( < 144 printf("Case #~A: ", C), < 145 let RkN := readLine() in solve(RkN[1], RkN[2], RkN[3], r < 146 princ("\n") < 147 ) < 148 ] < 149 < 150 (main()) <
Deleted _lib/gcj/!gcj-smpl.cs version [2cc6fccce968278d]
1 using System; < 2 using System.Linq; < 3 < 4 class C < 5 { < 6 static void Main() < 7 { < 8 long[] Ts = readLongArray(); < 9 long T = Ts[0]; < 10 < 11 for(long C=1; C<=T; ++C) < 12 { < 13 long[] RkN = readLongArray(); < 14 long R = RkN[0]; < 15 long k = RkN[1]; < 16 long N = RkN[2]; < 17 long[] g = readLongArray(); < 18 < 19 Console.WriteLine("Case #{0}: {1}", C, solveSmall(R,k,N, < 20 } < 21 } < 22 < 23 static long[] readLongArray() < 24 { < 25 return (from s in Console.ReadLine().Split(' ') select long.Pars < 26 } < 27 < 28 static long solveSmall(long R, long k, long N, long[] g) < 29 { < 30 long totalEarn = 0; < 31 < 32 for(int i=0; i<R; ++i) < 33 { < 34 long ride = 0; < 35 for(int q=0; q<g.Length; ++q) < 36 if( ride + g[q] > k ) < 37 { < 38 g = rotate(g, q); < 39 break; < 40 } < 41 else < 42 { < 43 ride += g[q]; < 44 } < 45 totalEarn += ride; < 46 } < 47 < 48 return totalEarn; < 49 } < 50 < 51 static long[] rotate(long[] g, int s) < 52 { < 53 long[] g2 = new long[g.Length]; < 54 for(int i=s; i<g.Length; ++i) < 55 g2[i-s] = g[i]; < 56 for(int i=0; i<s; ++i) < 57 g2[i+g.Length-s] = g[i]; < 58 return g2; < 59 } < 60 } <
Deleted _lib/gcj/!gcj-smpl.vbs version [4dbab301b915fb0d]
1 ' < 2 ' Written in VBScript < 3 ' < 4 < 5 Function ReadLine() < 6 Dim s < 7 s = Split(WScript.StdIn.ReadLine, " ") < 8 For i = LBound(s) To UBound(s) < 9 s(i) = CLng(s(i)) < 10 Next < 11 ReadLine = s < 12 End Function < 13 < 14 Function Gcd(a, b) < 15 If a = 0 Then < 16 Gcd = b < 17 Else < 18 Gcd = Gcd(b mod a, a) < 19 End If < 20 End Function < 21 < 22 Function Solve(T) < 23 Dim g, r < 24 g = Abs(T(1) - T(2)) < 25 For i = 2 To UBound(T) < 26 g = Gcd(g, Abs(T(1) - T(i))) < 27 Next < 28 r = T(1) mod g < 29 If r = 0 Then < 30 Solve = 0 < 31 Else < 32 Solve = g - r < 33 End If < 34 End Function < 35 < 36 C = ReadLine()(0) < 37 For CaseID = 1 To C < 38 WScript.StdOut.WriteLine "Case #" & CaseID & ": " & Solve(ReadLine) < 39 Next <
Deleted _lib/gcj/!gcj-tmpl.cpp version [8b7e23cf8b869fd6]
1 //----------------------------------------------------------------------------- < 2 // >>Code Template<< (for Visual C++) < 3 < 4 #include <iostream> < 5 #include <sstream> < 6 #include <iomanip> < 7 #include <string> < 8 #include <vector> < 9 #include <set> < 10 #include <map> < 11 #include <algorithm> < 12 #include <numeric> < 13 #include <iterator> < 14 #include <complex> < 15 #include <functional> < 16 #include <queue> < 17 #include <stack> < 18 #include <cmath> < 19 #include <cassert> < 20 #include <cstring> < 21 #define cout os < 22 using namespace std; < 23 typedef long long LL; < 24 typedef complex<double> CMP; < 25 void END_OF_INPUT_FOR_THIS_TEST_CASE(); // stub for multi-threading < 26 < 27 //----------------------------------------------------------------------------- < 28 // >>Main<< < 29 < 30 void case_main( ostream& os ) < 31 { < 32 END_OF_INPUT_FOR_THIS_TEST_CASE(); < 33 } < 34 < 35 //----------------------------------------------------------------------------- < 36 // >>Code Template<< (Multi-Thread Solver) < 37 < 38 #if 1 < 39 #undef cout < 40 #include <windows.h> < 41 #include <process.h> < 42 < 43 static const int THREAD_NUM = 2; < 44 volatile int g_id; < 45 int g_nCase; < 46 CRITICAL_SECTION g_cs; < 47 vector<string> g_output; < 48 < 49 unsigned __stdcall thread_main( void* t_id ) { < 50 for(;;) { < 51 EnterCriticalSection(&g_cs); < 52 const int id = ++g_id; < 53 if(id>g_nCase) { LeaveCriticalSection(&g_cs); break; } < 54 cerr << setw(4) << id << " @ " << (int)t_id << " start" << endl; < 55 < 56 ostringstream ss; < 57 ss << "Case #" << id << ": "; < 58 case_main( ss ); < 59 < 60 EnterCriticalSection(&g_cs); < 61 if(g_output.size()<id) g_output.resize(id); < 62 g_output[id-1] = ss.str(); < 63 cerr << setw(4) << id << " @ " << (int)t_id << " end" << endl; < 64 LeaveCriticalSection(&g_cs); < 65 } < 66 return 0; < 67 } < 68 < 69 void END_OF_INPUT_FOR_THIS_TEST_CASE() { LeaveCriticalSection(&g_cs); } < 70 < 71 int main() { < 72 cin >> g_nCase; < 73 string dummy; getline(cin, dummy); < 74 < 75 InitializeCriticalSection(&g_cs); < 76 vector<HANDLE> thread; < 77 for(int i=0; i<THREAD_NUM; ++i) < 78 thread.push_back( (HANDLE)_beginthreadex(0, 0, &thread_main, (vo < 79 WaitForMultipleObjects( thread.size(), &thread[0], TRUE, INFINITE ); < 80 DeleteCriticalSection(&g_cs); < 81 < 82 copy( g_output.begin(), g_output.end(), ostream_iterator<string>(cout) ) < 83 } < 84 < 85 //----------------------------------------------------------------------------- < 86 // >>Code Template<< (Single-Thread Solver) < 87 < 88 #else < 89 #undef cout < 90 void END_OF_INPUT_FOR_THIS_TEST_CASE() {} < 91 int main() { < 92 int nCase; cin >> nCase; < 93 string dummy; getline(cin, dummy); < 94 < 95 for(int id=1; id<=nCase; ++id) { < 96 cout << "Case #" << id << ": "; < 97 case_main( cout ); < 98 } < 99 } < 100 #endif <
Deleted _lib/gcj/!gcj-tmpl.java version [e9cb1325b5300e50]
1 import java.io.*; < 2 import java.util.*; < 3 < 4 public class <CLASSNAME> < 5 { < 6 public static void main(String[] arg) < 7 { < 8 Scanner sc = new Scanner(System.in); < 9 int T = sc.nextInt(); < 10 for(int C=1; C<=T; ++C) < 11 { < 12 System.out.printf("Case #%d: ", C); < 13 (new <CLASSNAME>(sc)).caseMain(); < 14 } < 15 } < 16 < 17 Scanner sc; < 18 <CLASSNAME>( Scanner sc ) { this.sc = sc; } < 19 < 20 void caseMain() < 21 { < 22 int n = sc.nextInt(); < 23 long[] x = new long[n]; < 24 for(int i=0; i<n; ++i) x[i] = sc.nextInt(); < 25 long[] y = new long[n]; < 26 for(int i=0; i<n; ++i) y[i] = sc.nextInt(); < 27 < 28 System.out.println(solve(x, y, n)); < 29 } < 30 < 31 long solve(long[] x, long[] y, int n) < 32 { < 33 Arrays.sort(x); < 34 Arrays.sort(y); < 35 long s = 0; < 36 for(int i=0; i<n; ++i) < 37 s += x[i] * y[n-1-i]; < 38 return s; < 39 } < 40 } <
Deleted _lib/gcj/!gcj-tmpl.lua version [a2c96590b21d65bc]
1 CN = io.stdin:read("*n") < 2 for C=1, CN, 1 do < 3 io.stdout:write( string.format("Case #%d: ", C) ) < 4 < 5 N = io.stdin:read("*n") < 6 M = io.stdin:read("*n") < 7 < 8 fav = {} < 9 for i=1, M, 1 do < 10 T = io.stdin:read("*n") < 11 fav[i] = {} < 12 for j=1, T, 1 do < 13 X, Y = io.stdin:read("*n", "*n") < 14 fav[i][j] = {X, Y} < 15 end < 16 end < 17 < 18 io.stdout:write( string.format("%d %d\n", N, M) ) < 19 end <
Deleted _lib/gcj/!gcj-tmpl.py version [da8352105d588b93]
Deleted _lib/geo/area.cpp version [959cda21c7e42a70]
1 //------------------------------------------------------------- < 2 // Area of a polygon < 3 // O(N) < 4 // < 5 // Verified by < 6 // - SRM 337 Div1 LV3 < 7 // - SRM 486 Div1 LV3 < 8 //------------------------------------------------------------- < 9 < 10 double outer_prod( pt a, pt b ) < 11 { < 12 return (a.real()*b.imag() - b.real()*a.imag())/2; < 13 } < 14 < 15 double area( const vector<pt>& q ) < 16 { < 17 double a = 0.0; < 18 < 19 pt o = q[0]; < 20 for(int i=1; i+1<q.size(); ++i) < 21 a += outer_prod(q[i]-o, q[i+1]-o); < 22 return abs(a) / 2; < 23 } <
Deleted _lib/geo/ccw.cpp version [81dbefbd30f15e79]
1 //------------------------------------------------------------- < 2 // ccw < 3 // < 4 // Verified by < 5 // - SRM 492 Div1 LV1 < 6 //------------------------------------------------------------- < 7 < 8 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } < 9 double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } < 10 < 11 int ccw(const CMP& a, CMP b, CMP c) { < 12 b -= a; c -= a; < 13 if( outer_prod(b,c) > 0 ) return +1; // counter clockwise < 14 if( outer_prod(b,c) < 0 ) return -1; // clockwise < 15 if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line < 16 if( norm(b) < norm(c) ) return -2; // [a--b]--c on line < 17 return 0; // [a--c--b] on line < 18 } <
Deleted _lib/geo/circle_3pt.cpp version [40885cae01887a2c]
1 < 2 //------------------------------------------------------------- < 3 // The circle passing three points < 4 // < 5 // Verified by < 6 // - AOJ 0010 < 7 //------------------------------------------------------------- < 8 < 9 vector<double> solve_linear_eq( int n, vector< vector<double> > M, const vector< < 10 { < 11 vector<double> A(V); < 12 for(int i=0; i<n; ++i) < 13 { < 14 // pivot < 15 if( M[i][i] == 0 ) < 16 for(int j=i+1; j<n; ++j) < 17 if( M[j][i] != 0 ) < 18 {swap(M[i], M[j]); swap(A[i], A[j]); bre < 19 if( M[i][i] == 0 ) < 20 throw "no anser"; < 21 < 22 // M[i][i] <-- 1 < 23 double p = M[i][i]; < 24 for(int j=i; j<n; ++j) < 25 M[i][j] /= p; < 26 A[i] /= p; < 27 < 28 // M[*][i] <-- 0 < 29 for(int j=0; j<n; ++j) if(j!=i) < 30 { < 31 double r = M[j][i]; < 32 for(int k=i; k<n; ++k) < 33 M[j][k] -= M[i][k] * r; < 34 A[j] -= A[i] * r; < 35 } < 36 } < 37 return A; < 38 } < 39 < 40 void circle_3pt( CMP p1, CMP p2, CMP p3, CMP* c, double* r ) < 41 { < 42 p2 -= p1; < 43 p3 -= p1; < 44 // c == p2/2 + A p2 i == p3/2 + B p3 i < 45 < 46 vector< vector<double> > M(2, vector<double>(2)); < 47 vector<double> V(2); < 48 M[0][0] = -p2.imag(); M[0][1] = +p3.imag(); V[0] = (p3.real()-p2.real()) < 49 M[1][0] = +p2.real(); M[1][1] = -p3.real(); V[1] = (p3.imag()-p2.imag()) < 50 V = solve_linear_eq(2, M, V); < 51 < 52 double A=V[0], B=V[1]; < 53 *c = p1 + p2/2.0 + A * p2 * CMP(0,1); < 54 *r = abs(*c - p1); < 55 } <
Deleted _lib/geo/convexHull.cpp version [75743e110118c49c]
1 < 2 //------------------------------------------------------------- < 3 // Convex Hull -- Andrew's Monotone Chain < 4 // O(N log N) < 5 // < 6 // Verified by < 7 // - SRM 336 Div1 LV3 < 8 // - TCO09 Round2 LV2 < 9 // - SRM 486 Div1 LV3 < 10 //------------------------------------------------------------- < 11 < 12 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } < 13 double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } < 14 < 15 int ccw(const CMP& a, CMP b, CMP c) { < 16 b -= a; c -= a; < 17 if( outer_prod(b,c) > 0 ) return +1; // counter clockwise < 18 if( outer_prod(b,c) < 0 ) return -1; // clockwise < 19 if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line < 20 if( norm(b) < norm(c) ) return -2; // a--b--c on line < 21 return 0; < 22 } < 23 < 24 bool byX( const CMP& a, const CMP& b ) { < 25 if( a.real() != b.real() ) < 26 return a.real() < b.real(); < 27 return a.imag() < b.imag(); < 28 } < 29 < 30 vector<CMP> convex_hull( vector<CMP> p ) < 31 { < 32 #define IS_RIGHT <0 // skip on-line verts < 33 //#define IS_RIGHT ==-1 // take all < 34 < 35 sort(p.begin(), p.end(), &byX); < 36 < 37 vector<CMP> ans; < 38 for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right < 39 while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1] < 40 ans.pop_back(); < 41 if( ans.size() == p.size() ) < 42 return ans; < 43 for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left < 44 while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1] < 45 ans.pop_back(); < 46 ans.pop_back(); < 47 return ans; < 48 } <
Deleted _lib/geo/convexHull_old.cpp version [9ffbc36d1d4aa6a7]
1 < 2 //------------------------------------------------------------- < 3 // Convex Hull -- Gift Wrapping < 4 // O(N log N) < 5 // < 6 // ToDo : Rewrite by CCW... < 7 // < 8 // Verified by < 9 // - SRM 336 Div1 LV3 < 10 //------------------------------------------------------------- < 11 < 12 bool byY( CMP a, CMP b ) < 13 { < 14 if( a.imag() == b.imag() ) < 15 return a.real() < b.real(); < 16 return a.imag() < b.imag(); < 17 } < 18 < 19 bool byArg( CMP a, CMP b ) < 20 { < 21 return arg(a) < arg(b); < 22 } < 23 < 24 bool isRight( CMP a, CMP b, CMP c ) < 25 { < 26 return arg((c-b) / (b-a)) < 0; < 27 } < 28 < 29 vector<CMP> convex_hull( vector<CMP> p ) < 30 { < 31 vector<CMP>::iterator it = min_element( p.begin(), p.end(), byY ); < 32 CMP o = *it; < 33 p.erase(it); < 34 for(int i=0; i<p.size(); ++i) < 35 p[i] -= o; < 36 sort( p.begin(), p.end(), byArg ); < 37 < 38 vector<CMP> q; < 39 q.push_back( CMP(0,0) ); < 40 q.push_back( p[0] ); < 41 for(int i=1; i<p.size(); ++i) { < 42 while( isRight(q[q.size()-2], q[q.size()-1], p[i]) ) < 43 q.pop_back(); < 44 q.push_back( p[i] ); < 45 } < 46 for(int i=0; i<q.size(); ++i) < 47 q[i] += o; < 48 return q; < 49 } <
Deleted _lib/geo/pt_in_poly.cpp version [05f672d15009c4b5]
1 < 2 //------------------------------------------------------------- < 3 // The circle passing three points < 4 // < 5 // Verified by < 6 // - AOJ 0012 (only triangles) < 7 //------------------------------------------------------------- < 8 < 9 double outer_prod( CMP a, CMP b ) < 10 { < 11 return (a.real()*b.imag() - b.real()*a.imag())/2; < 12 } < 13 < 14 bool point_in_polygon( vector<CMP>& ps, CMP p ) < 15 { < 16 bool in = false; < 17 for(int i=0; i<ps.size(); ++i) { < 18 CMP a = ps[i] - p; < 19 CMP b = ps[(i+1)%ps.size()] - p; < 20 if(a.imag() > b.imag()) swap(a,b); < 21 if(a.imag()<=0 && 0<b.imag()) { < 22 if( outer_prod(a,b) < 0 ) < 23 in = !in; < 24 } < 25 //if( outer_prod(a,b)==0 && inner_prod(a,b)<=0 ) return ON; < 26 } < 27 return in; < 28 } <
Deleted _lib/graph/__goldberg.cpp version [3f97582085a591c3]
1 //---------------------------------------------------------------------------- < 2 // Goldberg(-Tarjan?) @ (ő嗬) < 3 // < 4 // eʕtOt G ł Src Dest ւ̍ő嗬ʂ߂ < 5 // - Ot͗אڍsœnƁBG ͔j܂B < 6 // - ʂłȂFloŵ~Ƃ G ̗eʂĂ镔 < 7 // < 8 // vZʂ < 9 // - O(V^3) < 10 // # ؖ͂܂ĂȂ < 11 // < 12 // ASY̊T < 13 // {`͈ȉ̒ʂ < 14 // 1. Ƃ肠SrcoĂӑSɗeʌE܂ŗ < 15 // 2. > o ȃm[hăoX < 16 // - Dest܂œBpXȂA < 17 // Destɋ߂iޕӂւ̗oʂ𑝂₷ < 18 // - ȂȂASrc߂痈ӂ < 19 // ʂ炷 < 20 // 3. 2.AoXȒ_ȂȂ܂ŌJԂ < 21 // u > o ȃm[hāv̏́AooXς < 22 // Queueɓ˂łƂFIFOłB < 23 // uDestɋ߂vuSrcɋ߂vɌɕ]Kv͂ȂāA < 24 // x̋ߎł\B̃R[hł͂̋ߎl d[] ŎĂB < 25 // d[] ̕]KxɂƂ肷heuristicsőȂ炵B < 26 // ƂȂƎۏ͎gɂȂȂ炵BƂłƂB < 27 //---------------------------------------------------------------------------- < 28 < 29 #include <vector> < 30 #include <queue> < 31 #include <limits> < 32 using namespace std; < 33 < 34 typedef int Vert; < 35 typedef int Capacity; < 36 typedef vector< vector<Capacity> > Graph; < 37 < 38 Capacity goldberg_tarjan( Graph& G, Vert Src, Vert Dest ) < 39 { < 40 vector<Capacity> e( G.size() ); // excess : - o < 41 vector<int> d( G.size() ); // distance : Destւ̋||Srcւ̋-N̉ < 42 d[Src] = G.size(); < 43 < 44 queue<Vert> Q; // e[v]>0 ȃm[hĂL[ < 45 < 46 // Ƃ肠SrcS͂ŗ < 47 for(int v=0; v!=G.size(); ++v) < 48 if( G[Src][v] ) < 49 { < 50 G[v][Src] += G[Src][v]; < 51 e[v] += G[Src][v]; < 52 G[Src][v] = 0; < 53 Q.push(v); < 54 } < 55 < 56 // e[v]>0 ȃm[hȂȂ܂ŌJԂ < 57 while( !Q.empty() ) < 58 { < 59 Vert v = Q.front(); < 60 < 61 for(int u=0; u!=G.size() && e[v]; ++u) < 62 if( G[v][u] && d[v]>d[u] ) // Kȕɗ "PUSH" < 63 { < 64 Capacity f = min(e[v], G[v][u]); < 65 G[v][u] -= f; < 66 G[u][v] += f; < 67 e[v] -= f; < 68 e[u] += f; < 69 if( e[u]==f && u!=Src && u!=Dest ) Q.push(u); < 70 } < 71 < 72 if( e[v] == 0 ) // oXꂽ̂ŃL[珜 < 73 Q.pop(); < 74 else // oXĂȂ̂͂̂d[v]Ă蒼 "RELABEL" < 75 { < 76 Capacity m = numeric_limits<Capacity>::max(); < 77 for(int u=0; u!=G.size(); ++u) < 78 if( G[v][u] ) < 79 m = min(m, d[u]+1); < 80 d[v] = m; < 81 } < 82 } < 83 < 84 // Dest ւ̗ʂԂ < 85 return e[Dest]; < 86 } < 87 < 88 //---------------------------------------------------------------------------- < 89 // PKU 1459 < 90 //---------------------------------------------------------------------------- < 91 < 92 #include <iostream> < 93 #include <locale> < 94 < 95 int main() < 96 { < 97 cin.imbue( std::locale("C") ); < 98 for(int n,np,nc,m; cin>>n>>np>>nc>>m;) < 99 { < 100 // 0: src, 1: dst, 2: ... < 101 Graph g(n+2, vector<Capacity>(n+2)); < 102 < 103 while(m--) < 104 { < 105 int u, v, z; char _; < 106 cin >> _ >> u >> _ >> v >> _ >> z; < 107 g[u+2][v+2] = z; < 108 } < 109 < 110 while(np--) < 111 { < 112 int u, z; char _; < 113 cin >> _ >> u >> _ >> z; < 114 g[0][u+2] = z; < 115 } < 116 < 117 while(nc--) < 118 { < 119 int u, z; char _; < 120 cin >> _ >> u >> _ >> z; < 121 g[u+2][1] = z; < 122 } < 123 < 124 cout << goldberg_tarjan(g, 0, 1) << endl; < 125 } < 126 } <
Deleted _lib/graph/biMatch.cpp version [de8fb2bb9f6a1b6d]
1 < 2 //------------------------------------------------------------- < 3 // Bipertite max-matching (by duality, min-vert-cover) < 4 // O(V E) < 5 // < 6 // Verified by < 7 // SRM 397 Div1 Lv3 < 8 //------------------------------------------------------------- < 9 < 10 typedef int vert; < 11 typedef vert edge; < 12 typedef vector<edge> edges; < 13 typedef vector<edges> graph; < 14 < 15 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) < 16 { < 17 for(int i=0; i<G[v].size(); ++i) { < 18 vert u = G[v][i]; < 19 if( visited[u] ) continue; < 20 visited[u] = true; < 21 < 22 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) < 23 { matchTo[v]=u, matchTo[u]=v; return true; } < 24 } < 25 return false; < 26 } < 27 < 28 template<int NV> < 29 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right < 30 // only left->right edges are used during computation < 31 { < 32 vector<vert> matchTo(G.size(), -1); < 33 int ans = 0; < 34 for(vert v=0; v<L; ++v) { < 35 bool visited[NV] = {}; < 36 if( augment(G, v, matchTo, visited) ) < 37 ++ans; < 38 } < 39 return ans; < 40 } <
Deleted _lib/graph/isGraphical.cpp version [5fae6e092a92d7c8]
1 //------------------------------------------------------------- < 2 // Check the given list can be a degree list of some graph < 3 // O(n^2) (I suspect it can be made faster, though...) < 4 // < 5 // Verified by < 6 // - SRM 398 Div1 LV3 < 7 // < 8 //(( < 9 // Havel-Hakimi < 10 // If G[0], ..., G[n] (decreasing) is graphical, < 11 // then G[1]-1, G[2]-1, ..., G[G[0]]-1, G[G[0]+1], .., G[n] < 12 // is also graphical. < 13 //)) < 14 //------------------------------------------------------------- < 15 < 16 bool isGraphical( vector<int> G ) < 17 { < 18 sort( G.begin(), G.end() ); < 19 < 20 vector<int>::iterator b = lower_bound( G.begin(), G.end(), 1 ); < 21 vector<int>::iterator e = G.end(); < 22 < 23 while( b < e ) < 24 { < 25 int n = *(--e); < 26 if( e-b < n ) < 27 return false; < 28 for(vector<int>::iterator i=e-n; i!=e; ++i) < 29 --*i; < 30 inplace_merge( b, e-n, e ); < 31 b = lower_bound( G.begin(), G.end(), 1 ); < 32 } < 33 return true; < 34 } <
Deleted _lib/graph/maxFlow.cpp version [c6d3325f9b7a789b]
1 < 2 //------------------------------------------------------------- < 3 // Dinic's Algorithm < 4 // O(V E) < 5 // < 6 // G : bidirectional (G[i].has(j) <==> G[j].has(i)) < 7 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 < 8 // < 9 // Verified by < 10 // - SRM 399 Div1 LV3 < 11 // - PKU 1459 < 12 // - CodeCraft 09 CUTS < 13 // - SRM 465 Div1 LV2 < 14 //------------------------------------------------------------- < 15 < 16 static const int NV = 512; < 17 typedef int flow; < 18 typedef int vert; < 19 typedef vert edge; < 20 typedef vector<edge> edges; < 21 typedef vector<edges> graph; < 22 typedef flow flow_graph[NV][NV]; < 23 < 24 flow dinic_dfs( graph& G, flow_graph F, vert v, vert D, < 25 int LV[], flow flow_in, int blocked[] ) < 26 { < 27 flow flow_out = 0; < 28 for(int i=0; i!=G[v].size(); ++i) { < 29 int u = G[v][i]; < 30 if( LV[v]+1==LV[u] && F[v][u] ) { < 31 flow f = min(flow_in-flow_out, F[v][u]); < 32 if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blo < 33 F[v][u] -= f; < 34 F[u][v] += f; < 35 flow_out += f; < 36 if( flow_in == flow_out ) return flow_out; < 37 } < 38 } < 39 } < 40 blocked[v] = (flow_out==0); < 41 return flow_out; < 42 } < 43 < 44 flow maxFlow( graph& G, flow_graph F, vert S, vert D ) < 45 { < 46 for( flow total=0 ;; ) { < 47 int LV[NV] = {0}; < 48 vector<int> Q(1, S); < 49 for(int lv=1; !Q.empty(); ++lv) { < 50 vector<int> Q2; < 51 for(int i=0; i!=Q.size(); ++i) { < 52 edges& ne = G[Q[i]]; < 53 for(int j=0; j!=ne.size(); ++j) < 54 if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j < 55 LV[ne[j]]=lv, Q2.push_back(ne[j] < 56 } < 57 Q.swap(Q2); < 58 } < 59 < 60 if( !LV[D] ) < 61 return total; < 62 < 63 int blocked[NV] = {}; < 64 total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked ); < 65 } < 66 } <
Deleted _lib/graph/mincostFlow.cpp version [a86509e21e3c5ec5]
1 //------------------------------------------------------------- < 2 // MinCost-MaxFlow < 3 // O(??) < 4 // < 5 // Verified by < 6 // - SRM 487 Div2 LV3 < 7 // - SRM 491 Div1 LV3 < 8 //------------------------------------------------------------- < 9 < 10 #include <iostream> < 11 #include <string> < 12 #include <vector> < 13 #include <map> < 14 #include <queue> < 15 using namespace std; < 16 < 17 template<typename T> < 18 class IdGen < 19 { < 20 map<T, int> v2id_; < 21 vector<T> id2v_; < 22 public: < 23 int v2id(const T& v) { < 24 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } < 25 return v2id_[v]; < 26 } < 27 const T& id2v(int i) const { return id2v_[i]; } < 28 int size() const { return id2v_.size(); } < 29 }; < 30 < 31 template<typename Vert, typename Cost, typename Flow, int NV=256> < 32 class MinCostFlow < 33 { < 34 IdGen<Vert> idgen; < 35 < 36 vector<int> G[NV]; < 37 Flow F[NV][NV]; < 38 Cost C[NV][NV]; < 39 < 40 public: < 41 void addEdge( Vert s_, Vert t_, Cost c, Flow f ) < 42 { < 43 int s = idgen.v2id(s_), t = idgen.v2id(t_); < 44 G[s].push_back(t); < 45 G[t].push_back(s); < 46 C[s][t] = c; < 47 C[t][s] = -c; < 48 F[s][t] = f; < 49 F[t][s] = 0; < 50 } < 51 < 52 pair<Cost, Flow> calc( Vert s_, Vert t_ ) < 53 { < 54 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); < 55 static const Cost COST_INF = 1e+300; // !!EDIT HERE!! < 56 static const Flow FLOW_INF = 0x7fffffff; < 57 < 58 Cost total_cost = 0; < 59 Flow total_flow = 0; < 60 vector<Cost> h(N, 0); // potential < 61 for(Flow RF=FLOW_INF; RF>0; ) // residual flow < 62 { < 63 // Dijkstra -- find the min-cost path < 64 vector<Cost> d(N, COST_INF); d[S] = 0; < 65 vector<int> prev(N, -1); < 66 < 67 typedef pair< Cost, pair<int,int> > cedge; < 68 priority_queue< cedge, vector<cedge>, greater<cedge> > Q < 69 Q.push( cedge(0, make_pair(S,S)) ); < 70 while( !Q.empty() ) { < 71 cedge e = Q.top(); Q.pop(); < 72 if( prev[e.second.second] >= 0 ) < 73 continue; < 74 prev[e.second.second] = e.second.first; < 75 < 76 int u = e.second.second; < 77 for(int i=0; i<G[u].size(); ++i) { < 78 int v = G[u][i]; < 79 Cost r_cost = C[u][v] + h[u] - h[v]; < 80 if( F[u][v] > 0 && d[v] > d[u]+r_cost ) < 81 Q.push( cedge(d[v]=d[u]+r_cost, < 82 } < 83 } < 84 < 85 if( prev[T] < 0 ) < 86 break; // Finished < 87 < 88 // Run the flow as much as possible < 89 Flow f = RF; < 90 for(int u=T; u!=S; u=prev[u]) < 91 f = min(f, F[prev[u]][u]); < 92 RF -= f; < 93 total_flow += f; < 94 < 95 for(int u=T; u!=S; u=prev[u]) < 96 { < 97 total_cost += f * C[prev[u]][u]; < 98 F[prev[u]][u] -= f; < 99 F[u][prev[u]] += f; < 100 } < 101 < 102 // Update the potential < 103 for(int u=0; u<N; ++u) < 104 h[u] += d[u]; < 105 } < 106 return make_pair(total_cost, total_flow); < 107 } < 108 }; <
Deleted _lib/graph/undAllPairMinCut.cpp version [08ac17a6157e8d09]
1 < 2 //------------------------------------------------------------- < 3 // Gomory-Hu < 4 // All Pair Minimum Cuts for an Undirected Graph < 5 // O(V^4) < 6 // < 7 // G : undirected (G[i].has(j) <==> G[j].has(i)) < 8 // F : flow-capacity F[i][j] = F[j][i] = Capacity < 9 // < 10 // Verified by < 11 // - CodeCraft 09 CUTS < 12 //------------------------------------------------------------- < 13 < 14 static const int NV = 512; < 15 typedef int flow; < 16 typedef int vert; < 17 typedef vert edge; < 18 typedef vector<edge> edges; < 19 typedef vector<edges> graph; < 20 typedef flow flow_graph[NV][NV]; < 21 < 22 flow_graph GHF; < 23 void GomoryHu( graph& G, flow_graph F, flow_graph AllPairMinCut ) < 24 { < 25 int N = G.size(); < 26 vector<vert> parent(N, 0); < 27 vector<flow> weight(N, 0); < 28 < 29 // construct the Gomory-Hu Tree < 30 for(vert s=1; s<N; ++s) < 31 { < 32 vert t = parent[s]; < 33 < 34 // mincut between s and t < 35 memcpy(GHF, F, sizeof(GHF)); < 36 flow mincut = 0; < 37 for(;;) { < 38 // bfs < 39 vector<vert> prev(N, -1); prev[s]=s; < 40 queue<vert> Q; Q.push(s); < 41 while( !Q.empty() ) { < 42 vert v = Q.front(); Q.pop(); < 43 for(int i=0; i<G[v].size(); ++i) { < 44 vert u = G[v][i]; < 45 if( prev[u]==-1 && GHF[v][u] ) < 46 prev[u]=v, Q.push(u); < 47 } < 48 } < 49 < 50 if( prev[t] == -1 ) < 51 { < 52 // done: separeted to {v|prev[v]!=-1} and {v|pre < 53 // split t's children < 54 weight[s] = mincut; < 55 for(vert v=0; v<N; ++v) < 56 if( parent[v]==t && prev[v]!=-1 && v!=s < 57 parent[v] = s; < 58 vert pt = parent[t]; < 59 if( prev[pt]!=-1 ) < 60 parent[s]=pt, parent[t]=s, weight[s]=wei < 61 break; < 62 } < 63 < 64 // flow... < 65 flow cur = 0x7fffffff; < 66 for(vert v=t; v!=s; v=prev[v]) < 67 cur = min(cur, GHF[prev[v]][v]); < 68 for(vert v=t; v!=s; v=prev[v]) < 69 GHF[prev[v]][v] -= cur, GHF[v][prev[v]] += cur; < 70 mincut += cur; < 71 } < 72 } < 73 < 74 // AllPairMinCuts over the G-H tree < 75 for(vert s=0; s<N; ++s) { < 76 vector<vert> ps_s; < 77 for(vert v=s ;; v=parent[v]) < 78 { ps_s.push_back(v); if( v==parent[v] ) break; } < 79 reverse(ps_s.begin(), ps_s.end()); < 80 < 81 for(vert t=s+1; t<N; ++t) { < 82 vector<vert> ps_t; < 83 for(vert v=t ;; v=parent[v]) < 84 { ps_t.push_back(v); if( v==parent[v] ) break; } < 85 reverse(ps_t.begin(), ps_t.end()); < 86 < 87 vert ca; < 88 for(int i=0; i<ps_s.size() && i<ps_t.size() && ps_s[i]== < 89 ca = ps_s[i]; < 90 < 91 flow s_to_root = 0x7fffffff, t_to_root = 0x7fffffff; < 92 for(vert v=s; v!=ca; v=parent[v]) < 93 s_to_root = min(s_to_root, weight[v]); < 94 for(vert v=t; v!=ca; v=parent[v]) < 95 t_to_root = min(t_to_root, weight[v]); < 96 AllPairMinCut[s][t] = AllPairMinCut[t][s] = min(s_to_roo < 97 } < 98 } < 99 } <
Deleted _lib/graph/undMinCut.cpp version [27b1f3ac721526bc]
1 < 2 //------------------------------------------------------------- < 3 // Stoer-Wagner < 4 // Minimum cost for making the graph unconnected < 5 // O(V^3) < 6 // < 7 // G : bidirectional (G[v][u] == G[u][v]) < 8 // < 9 // Verified by < 10 // - SRM 340 Div1 LV3 < 11 //------------------------------------------------------------- < 12 < 13 typedef int cost; < 14 typedef int vert; < 15 typedef vector< vector<cost> > graph; < 16 < 17 cost bidi_minCut( graph G, int N ) < 18 { < 19 vector<vert> V; < 20 for(int v=0; v<N; ++v) < 21 V.push_back(v); < 22 < 23 cost result = 0x7fffffff; < 24 for(int n=N; n>1; --n) < 25 { < 26 // invariant: < 27 // the current set of vertices = {V[0] .. V[n-1]} < 28 < 29 // order the vertices < 30 // v0 = 0 (arbitrary), < 31 // v1 = (u that maximizes \Sigma G[v0][u]) < 32 // v2 = (u that maximizes \Sigma G[v0][u]+G[v1][u]) < 33 // ... < 34 // vn-2 < 35 // vn-1 = (maximizes lastCut = \Sigma G[v0][u]+G[vn-2][u]) < 36 vector<int> vs; < 37 cost lastCut = 0; < 38 { < 39 vector<cost> ws(n, 0); < 40 ws[0] = 1; < 41 < 42 for(int i=0; i<n; ++i) { < 43 int j = max_element(ws.begin(), ws.end()) - ws.b < 44 lastCut = ws[j]; < 45 < 46 vs.push_back(j); < 47 ws[j] = -1; < 48 for(int k=0; k<n; ++k) < 49 if( ws[k] != -1 ) < 50 ws[k] += G[V[k]][V[j]]; < 51 } < 52 } < 53 < 54 // update mincut < 55 // lemma: "the min cost for separating vn-2 and vn-1"==lastCut < 56 result = min(result, lastCut); < 57 < 58 // reduce the graph (unify vn-2 and vn-1) < 59 // for testing the case vn-2 and vn-1 is connected < 60 vert v2=vs[n-2], v1=vs[n-1]; < 61 for(int i=0; i<n; ++i) { < 62 G[V[v2]][V[i]] += G[V[v1]][V[i]]; < 63 G[V[i]][V[v2]] += G[V[i]][V[v1]]; < 64 } < 65 V.erase( V.begin() + v1 ); < 66 } < 67 return result; < 68 } <
Deleted _lib/numeric/bigintFake.cpp version [029a85274b27ccda]
1 < 2 string add(const string& a, const string& b) < 3 { < 4 int n = max(a.size(), b.size()), carry=0; < 5 string c(n, '0'); < 6 for(int i=0; i<n; ++i) { < 7 int x = (a.size()<=i ? 0 : a[a.size()-1-i]-'0') < 8 + (b.size()<=i ? 0 : b[b.size()-1-i]-'0') + carry; < 9 c[n-1-i] = char('0'+x%10); < 10 carry = x/10; < 11 } < 12 if( carry ) c = char('0'+carry)+c; < 13 return c; < 14 } <
Deleted _lib/numeric/erathos.cpp version [451164162aaf4750]
Deleted _lib/numeric/fft.cpp version [30aac07db1a49b69]
1 < 2 //------------------------------------------------------------- < 3 // Fast Discrete Fourier Transform < 4 // O(n log n) < 5 // n must be a power of 2. < 6 // < 7 // Verified by < 8 // - SRM 436 LV3 < 9 //------------------------------------------------------------- < 10 < 11 CMP tmp[65536*4]; < 12 < 13 template<int F> < 14 void fft_impl( CMP a[], int n, int stride = 1 ) < 15 { < 16 if( n > 1 ) < 17 { < 18 CMP *ev=a, *od=a+stride; < 19 int s2=stride*2, n2=n/2; < 20 < 21 fft_impl<F>( ev, n2, s2 ); < 22 fft_impl<F>( od, n2, s2 ); < 23 < 24 for(int i=0; i<n; ++i) tmp[i] = ev[s2*(i%n2)] + od[s2*(i%n2)]*po < 25 for(int i=0; i<n; ++i) a[stride*i] = tmp[i]; < 26 } < 27 } < 28 < 29 void fft( vector<CMP>& a ) < 30 { < 31 fft_impl<+1>(&a[0], a.size()); < 32 } < 33 < 34 void ifft( vector<CMP>& a ) < 35 { < 36 fft_impl<-1>(&a[0], a.size()); < 37 for(int i=0; i<a.size(); ++i) < 38 a[i] /= a.size(); < 39 } <
Deleted _lib/numeric/gcd_lcm.cpp version [9e6d3cbd67078cb9]
1 LL gcd(LL a, LL b) < 2 { < 3 while(a) < 4 swap(a, b%=a); < 5 return b; < 6 } < 7 < 8 LL lcm(LL a, LL b) < 9 { < 10 return a/gcd(a,b)*b; < 11 } < 12 < 13 // Assumption: (a/b)*b+(a%b) == a < 14 // For typical C/C++ compilers, % on negatives satisfies this. < 15 // To be sure, replace a%b by a-a/b*b < 16 < 17 LL xgcd(LL a, LL b, LL* x, LL* y) // ax+by=g < 18 { < 19 if(b) { < 20 LL yy, g = xgcd(b,a%b,&yy,x); < 21 *y = yy - a/b**x; < 22 return g; < 23 } < 24 else { < 25 *x=1, *y=0; < 26 return a; < 27 } < 28 } <
Deleted _lib/numeric/linearEq.cpp version [908cbaac8fbb72e4]
1 < 2 //------------------------------------------------------------- < 3 // Linear Equation Solver < 4 // O(n^3) < 5 // < 6 // Verified by < 7 // - SRM 398 Div1 LV3 < 8 // - AOJ 0004 < 9 //------------------------------------------------------------- < 10 < 11 vector<double> solve_linear_eq( int n, vector< vector<double> > M, const vector< < 12 { < 13 vector<double> A(V); < 14 for(int i=0; i<n; ++i) < 15 { < 16 // pivot < 17 if( M[i][i] == 0 ) < 18 for(int j=i+1; j<n; ++j) < 19 if( M[j][i] != 0 ) < 20 {swap(M[i], M[j]); swap(A[i], A[j]); bre < 21 if( M[i][i] == 0 ) < 22 throw "no anser"; < 23 < 24 // M[i][i] <-- 1 < 25 double p = M[i][i]; < 26 for(int j=i; j<n; ++j) < 27 M[i][j] /= p; < 28 A[i] /= p; < 29 < 30 // M[*][i] <-- 0 < 31 for(int j=0; j<n; ++j) if(j!=i) < 32 { < 33 double r = M[j][i]; < 34 for(int k=i; k<n; ++k) < 35 M[j][k] -= M[i][k] * r; < 36 A[j] -= A[i] * r; < 37 } < 38 } < 39 return A; < 40 } <
Deleted _lib/numeric/linearEq2.cpp version [bf7f1d164fa34636]
1 //------------------------------------------------------------- < 2 // Linear Equation Solver for Teplitz Matrix < 3 // O(n^2) < 4 // < 5 // Faster solver for matrices satisfying < 6 // M[i][j] == M[i+1][j+1] < 7 // for all i, j>0 < 8 // Be careful that this implementation does not support the < 9 // case M[0][0]=M[1][1]=...=0. (zero-division) < 10 // < 11 // TODO: support M[0][0]=M[1][1]=...=0 < 12 // QUICKHACK: < 13 // find the least degenerated k and < 14 // calc initial vectors by gauss_jordan... < 15 // < 16 // Verified by < 17 // - (Checked by random data to match with linearEq.cpp) < 18 //------------------------------------------------------------- < 19 < 20 vector<double> solve_teplitz( int n, vector< vector<double> > M, const vector<do < 21 { < 22 vector<double> f, b, x; < 23 < 24 // invariants < 25 // M|k f|k = (1 0 ... 0) < 26 // M|k b|k = (0 ... 0 1) < 27 // M|k x|k = V|k < 28 f.push_back( 1 / M[0][0] ); < 29 b.push_back( 1 / M[0][0] ); < 30 x.push_back( V[0] / M[0][0] ); < 31 < 32 for(int k=2; k<=n; ++k) < 33 { < 34 // M|k (f|k-1 0) = (1 0 ... 0 ea) < 35 double ea = 0; < 36 for(int i=0; i<k-1; ++i) < 37 ea += M[k-1][i] * f[i]; < 38 < 39 // M|k (0 b|k-1) = (eb 0 ... 0 1) < 40 double eb = 0; < 41 for(int i=1; i<k; ++i) < 42 eb += M[0][i] * b[i-1]; < 43 < 44 // u(1 ea) + v(eb 1) = (1 0) < 45 //==> u = 1 / (1-ea.eb), v = -ea /(1-ea.eb) < 46 double u = 1/(1-ea*eb), v = -ea/(1-ea*eb); < 47 vector<double> ff; < 48 for(int i=0; i<k; ++i) < 49 ff.push_back( u*(i<k-1 ? f[i] : 0) + v*(i>0 ? b[i-1] : 0 < 50 < 51 // similarly... < 52 u = -eb/(1-ea*eb), v = 1/(1-ea*eb); < 53 vector<double> bb; < 54 for(int i=0; i<k; ++i) < 55 bb.push_back( u*(i<k-1 ? f[i] : 0) + v*(i>0 ? b[i-1] : 0 < 56 < 57 // update < 58 f.swap(ff); < 59 b.swap(bb); < 60 < 61 // M|k (x|k 0) (V|k ec) < 62 double ec = 0; < 63 for(int i=0; i<k-1; ++i) < 64 ec += M[k-1][i] * x[i]; < 65 x.push_back(0); < 66 for(int i=0; i<k; ++i) < 67 x[i] -= b[i] * (ec-V[k-1]); < 68 } < 69 < 70 return x; < 71 } <
Deleted _lib/numeric/matrix.cpp version [2c92483914a46a56]
1 < 2 //------------------------------------------------------------- < 3 // Matrix Operations < 4 // < 5 // Verified by < 6 // - SRM342 Div1 LV3 < 7 // - SRM341 Div1 LV3 < 8 // - SRM338 Div1 LV2 < 9 //------------------------------------------------------------- < 10 < 11 vector<LL> vMul( const vector< vector<LL> >& A, const vector<LL>& B ) < 12 { < 13 const int n = A.size(); < 14 < 15 vector<LL> C(n); < 16 for(int i=0; i<n; ++i) < 17 for(int j=0; j<n; ++j) < 18 C[i] += A[i][j] * B[j]; < 19 return C; < 20 } < 21 < 22 vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<L < 23 { < 24 const int n = A.size(); < 25 < 26 vector< vector<LL> > C(n, vector<LL>(n)); < 27 for(int i=0; i<n; ++i) < 28 for(int j=0; j<n; ++j) { < 29 LL Cij = 0; < 30 for(int k=0; k<n; ++k) < 31 Cij += A[i][k] * B[k][j]; < 32 C[i][j] = Cij; < 33 } < 34 return C; < 35 } < 36 < 37 vector< vector<LL> > mPow( vector< vector<LL> > M, LL t ) // t>0 < 38 { < 39 vector< vector<LL> > R; < 40 for(; t; t>>=1, M=mMul(M,M)) < 41 if( t&1 ) < 42 R = (R.empty() ? M : mMul(R,M)); < 43 return R; < 44 } < 45 < 46 vector< vector<LL> > mAdd( const vector< vector<LL> >& A, const vector< vector<L < 47 { < 48 const int n = A.size(); < 49 < 50 vector< vector<LL> > C(n, vector<LL>(n)); < 51 for(int i=0; i<n; ++i) < 52 for(int j=0; j<n; ++j) < 53 C[i][j] = A[i][j] + B[i][j]; < 54 return C; < 55 } <
Deleted _lib/numeric/mebius.cpp version [daa89aa8f6eb3e5c]
1 < 2 //------------------------------------------------------------- < 3 // Mebius Function < 4 // O( sqrt(N) ) < 5 // < 6 // mebius(n) = 0 if n=0 mod p*p for some p < 7 // mebius(n) = (-1)^k otherwise, where k is the number of n's prime factors < 8 // < 9 // properties: < 10 // 1: mebius(nm) = mebius(n) mebius(m) if gcd(n,m)=1 < 11 // 2: f(n) = Sigma_{d|n} g(d) < 12 // <=> < 13 // g(n) = Sigma_{d|n} f(d)mebius(n/d) < 14 // < 15 // Verified by < 16 // - CodeCraft '11 PSTR < 17 // < 18 // Further memoization or more might be needed. < 19 //------------------------------------------------------------- < 20 < 21 int mebius(int n) < 22 { < 23 int f = 1; < 24 for(int q=2; q*q<=n; ++q) < 25 if( n%q == 0 ) < 26 { < 27 if( n%(q*q) == 0 ) < 28 return 0; < 29 n /= q; < 30 f *= -1; < 31 } < 32 if(n>1) < 33 f *= -1; < 34 return f; < 35 } < 36 <
Deleted _lib/numeric/modArith.cpp version [b348fa4dbce4653d]
1 < 2 //------------------------------------------------------------- < 3 // Modulo Arithmetics < 4 // < 5 // Verified by < 6 // - TCO10 R3 LV3 < 7 //------------------------------------------------------------- < 8 < 9 static const int MODVAL = 1000000007; // op/ depends on primarity of the MODVAL < 10 struct mint < 11 { < 12 int val; < 13 mint():val(0){} < 14 mint(int x):val(x%MODVAL) {} < 15 mint(LL x):val(x%MODVAL) {} < 16 }; < 17 < 18 mint operator+(mint x, mint y) { return x.val+y.val; } < 19 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } < 20 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } < 21 mint POW(mint x, int e) { < 22 mint v = 1; < 23 for(;e;x=x*x,e>>=1) < 24 if(e&1) < 25 v=v*x; < 26 return v; < 27 } < 28 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } < 29 < 30 vector<mint> FAC_(1,1); < 31 void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); < 32 mint FAC(mint x) { return FAC_[x.val]; } < 33 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * < 34 < 35 /* < 36 // MODVAL must be a prime!! < 37 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e < 38 { < 39 if( b > e ) return 0; < 40 if( k <= 1 ) return k*(e-b+1); < 41 return DIV(SUB(POW(k, e+1), POW(k,b)), k-1); < 42 } < 43 < 44 LL Cpascal(LL n, LL k) < 45 { < 46 vector< vector<LL> > c(n+1, vector<LL>(k+1)); < 47 for(LL nn=1; nn<=n; ++nn) < 48 for(LL kk=0; kk<=min(nn,k); ++kk) < 49 c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[n < 50 return c[n][k]; < 51 } < 52 < 53 vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b) < 54 { < 55 int N = a.size(); < 56 vector< vector<LL> > c(N, vector<LL>(N)); < 57 for(int i=0; i<N; ++i) < 58 for(int j=0; j<N; ++j) < 59 for(int k=0; k<N; ++k) < 60 c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j])); < 61 return c; < 62 } < 63 < 64 // works for non-prime MODVAL < 65 LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1 < 66 { < 67 vector< vector<LL> > v(2, vector<LL>(2)); < 68 vector< vector<LL> > x(2, vector<LL>(2)); < 69 v[0][0] = v[1][1] = 1; < 70 x[0][0] = x_; x[0][1] = 0; < 71 x[1][0] = 1 ; x[1][1] = 1; < 72 for(;e;x=MATMUL(x,x),e>>=1) < 73 if(e&1) < 74 v = MATMUL(v, x); < 75 return v[1][0]; < 76 } < 77 < 78 // works for non-prime MODVAL < 79 LL HYP(LL x_, LL e) // e x^0 + (e-1) x^1 + ... + 1 x^e-1 = GEO(x,1)+GEO(x,2)+... < 80 { < 81 vector< vector<LL> > v(3, vector<LL>(3)); < 82 vector< vector<LL> > x(3, vector<LL>(3)); < 83 v[0][0] = v[1][1] = v[2][2] = 1; < 84 x[0][0] = x_; x[0][1] = 0; x[0][2] = 0; < 85 x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0; < 86 x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1; < 87 e++; < 88 for(;e;x=MATMUL(x,x),e>>=1) < 89 if(e&1) < 90 v = MATMUL(v, x); < 91 return v[2][0]; < 92 } < 93 */ <
Deleted _lib/numeric/modArithOld.cpp version [b669f317babaf285]
1 < 2 //------------------------------------------------------------- < 3 // Modulo Arithmetics < 4 // < 5 // Verified by < 6 // - SRM 397 Div1 LV2 < 7 // - SRM 428 Div1 LV2 < 8 // - CodeCraft 2010 CNTINT DRAW < 9 //------------------------------------------------------------- < 10 < 11 static const LL MODVAL = 1000000007; // must fit in 32-bits < 12 < 13 LL ADD(LL x, LL y) { return (x+y)%MODVAL; } < 14 LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; } < 15 LL MUL(LL x, LL y) { return (x*y)%MODVAL; } < 16 LL POW(LL x, LL e) { < 17 LL v = 1; < 18 for(;e;x=MUL(x,x),e>>=1) < 19 if(e&1) < 20 v = MUL(v, x); < 21 return v; < 22 } < 23 < 24 // MODVAL must be a prime!! < 25 LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); } < 26 < 27 // MODVAL must be a prime!! < 28 LL C(LL n, LL k) { < 29 LL v = 1; < 30 for(LL i=1; i<=k; ++i) < 31 v = DIV(MUL(v, n-i+1), i); < 32 return v; < 33 } < 34 < 35 // MODVAL must be a prime!! < 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e < 37 { < 38 if( b > e ) return 0; < 39 if( k <= 1 ) return k*(e-b+1); < 40 return DIV(SUB(POW(k, e+1), POW(k,b)), k-1); < 41 } < 42 < 43 < 44 < 45 < 46 LL Cpascal(LL n, LL k) < 47 { < 48 vector< vector<LL> > c(n+1, vector<LL>(k+1)); < 49 for(LL nn=1; nn<=n; ++nn) < 50 for(LL kk=0; kk<=min(nn,k); ++kk) < 51 c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[n < 52 return c[n][k]; < 53 } < 54 < 55 vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b) < 56 { < 57 int N = a.size(); < 58 vector< vector<LL> > c(N, vector<LL>(N)); < 59 for(int i=0; i<N; ++i) < 60 for(int j=0; j<N; ++j) < 61 for(int k=0; k<N; ++k) < 62 c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j])); < 63 return c; < 64 } < 65 < 66 // works for non-prime MODVAL < 67 LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1 < 68 { < 69 vector< vector<LL> > v(2, vector<LL>(2)); < 70 vector< vector<LL> > x(2, vector<LL>(2)); < 71 v[0][0] = v[1][1] = 1; < 72 x[0][0] = x_; x[0][1] = 0; < 73 x[1][0] = 1 ; x[1][1] = 1; < 74 for(;e;x=MATMUL(x,x),e>>=1) < 75 if(e&1) < 76 v = MATMUL(v, x); < 77 return v[1][0]; < 78 } < 79 < 80 // works for non-prime MODVAL < 81 LL HYP(LL x_, LL e) // e x^0 + (e-1) x^1 + ... + 1 x^e-1 = GEO(x,1)+GEO(x,2)+... < 82 { < 83 vector< vector<LL> > v(3, vector<LL>(3)); < 84 vector< vector<LL> > x(3, vector<LL>(3)); < 85 v[0][0] = v[1][1] = v[2][2] = 1; < 86 x[0][0] = x_; x[0][1] = 0; x[0][2] = 0; < 87 x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0; < 88 x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1; < 89 e++; < 90 for(;e;x=MATMUL(x,x),e>>=1) < 91 if(e&1) < 92 v = MATMUL(v, x); < 93 return v[2][0]; < 94 } <
Deleted _lib/numeric/nextComb.cpp version [291928c806737930]
1 //------------------------------------------------------------- < 2 // Next Combination < 3 // < 4 // Verified by < 5 // - SRM345 Div1 LV3 < 6 //------------------------------------------------------------- < 7 < 8 LL next_combination(LL p) < 9 { < 10 assert( p > 0 ); < 11 LL lsb = p & -p; < 12 LL rem = p + lsb; < 13 LL rit = rem & ~p; < 14 return rem | (rit/lsb >> 1)-1; < 15 } <
Deleted _lib/numeric/sternBrocot.cpp version [bfa0be1fa6ea3c75]
1 < 2 //------------------------------------------------------------- < 3 // Enumerate all positive reduced fractions in a < 4 // systematic manner. < 5 // [pl/ql, pr/qr] --> [pl/ql, pm/qm] + [pm/qm, pr/qr] < 6 // --> ... < 7 // < 8 // Verified by < 9 // - CodeCraft 09 FRACTION < 10 //------------------------------------------------------------- < 11 < 12 void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0) < 13 { < 14 LL pm = pl + pr, qm = ql + qr; < 15 sternBrocot(pl, ql, pm, qm); < 16 sternBrocot(pm, qm, pr, qr); < 17 } < 18 < 19 /* < 20 bool fleq(LL p1, LL q1, LL p2, LL q2) < 21 { < 22 return p1*q2 <= p2*q1; < 23 } < 24 < 25 void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0) < 26 { < 27 for(;;) { < 28 LL pm = pl + pr, qm = ql + qr; < 29 < 30 if( fleq(c,d,pm,qm) ) { < 31 // pr = pm, qr = qm; // [pl/ql, pm/qm] < 32 LL X = c*ql - d*pl; < 33 LL Y = d*pr - c*qr; < 34 LL k = max(1LL, Y/X); < 35 pr += k*pl; < 36 qr += k*ql; < 37 } < 38 else if( fleq(pm,qm,a,b) ) { < 39 // pl = pm, ql = qm; // [pm/qm, pr/qr] < 40 LL X = b*pr - a*qr; < 41 LL Y = a*ql - b*pl; < 42 LL k = max(1LL, Y/X); < 43 pl += k*pr; < 44 ql += k*qr; < 45 } < 46 else { < 47 cout << pm+qm*base << "/" << qm << endl; < 48 break; < 49 } < 50 } < 51 } < 52 */ <
Deleted _lib/typical/amap.cpp version [8e84d319ff86cb61]
1 // < 2 // accumulative map < 3 // basically a map<K,V>, but it eliminates duplication lazily < 4 // first keep all inserted elements in a vector. only when the buffer < 5 // overflows, it eliminates duplication < 6 // < 7 < 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> < 9 struct amap < 10 { < 11 typedef typename vector< pair<K,V> >::iterator iterator; < 12 < 13 vector< pair<K,V> > kv; < 14 amap() { kv.reserve(LIMIT); } < 15 < 16 void add(const K& k, const V& v) < 17 { < 18 kv.push_back( make_pair(k,v) ); < 19 if( kv.size() == LIMIT ) < 20 normalize(); < 21 } < 22 < 23 iterator begin() { return kv.begin(); } < 24 iterator end() { return kv.end(); } < 25 void swap( amap& rhs ) { kv.swap(rhs.kv); } < 26 < 27 // Tested: SRM 469 Lv3 < 28 void normalize() < 29 { < 30 sort(kv.begin(), kv.end()); < 31 int i=0; < 32 for(int j=0; j<kv.size(); ++i) < 33 { < 34 int k = j; < 35 kv[i] = kv[k]; < 36 while( ++j<kv.size() && kv[k].first==kv[j].first ) < 37 kv[i].second += kv[j].second; < 38 } < 39 kv.resize(i); < 40 } < 41 /* < 42 // Not Tested (Prefer First) < 43 void normalize() < 44 { < 45 sort(kv.begin(), kv.end()); < 46 int i=0; < 47 for(int j=0; j<kv.size(); ++i) < 48 { < 49 int k = j; < 50 kv[i] = kv[k]; < 51 while( ++j<kv.size() && kv[k].first==kv[j].first ) < 52 {} < 53 } < 54 kv.resize(i); < 55 } < 56 < 57 // Not Tested (Prefer Last) < 58 void normalize() < 59 { < 60 sort(kv.begin(), kv.end()); < 61 int i=0; < 62 for(int j=0; j<kv.size(); ++i) < 63 { < 64 int k = j; < 65 while( ++j<kv.size() && kv[k].first==kv[j].first ) < 66 {} < 67 kv[i] = kv[j-1]; < 68 } < 69 kv.resize(i); < 70 } < 71 */ < 72 }; <
Deleted _lib/typical/bfs.cpp version [b584e6b7fe45956b]
1 // code template for BFS < 2 < 3 State start = /*start*/; < 4 vector<State> Q( 1, start ); < 5 set<State> V; V.insert(start); < 6 < 7 for(int step=0; !Q.empty(); ++step) < 8 { < 9 vector<State> Qold; Qold.swap(Q); < 10 for(int qi=0; qi<Qold.size(); ++qi) < 11 { < 12 State& cur = Qold[qi]; < 13 if( /*isGoal(cur)*/ ) < 14 { < 15 } < 16 < 17 foreach(next) < 18 { < 19 if( !V.count(next) ) < 20 { < 21 V.insert(next); < 22 Q.push_back(next); < 23 } < 24 } < 25 } < 26 } <
Deleted _lib/typical/bitop.cpp version [80d6730d2c161aa4]
Deleted _lib/typical/comb.cpp version [d63ada0513560bce]
1 //------------------------------------------------------------- < 2 // number of combinations choosing k out of n < 3 // # you might better consider to use Pascal's triangle < 4 // # for comb modulo some number... < 5 // < 6 // Verified by < 7 // - SRM 350 Div1 LV2 < 8 //------------------------------------------------------------- < 9 < 10 LL comb(LL n, LL k) < 11 { < 12 k = min(k, n-k); < 13 < 14 LL c = 1; < 15 for(LL i=0; i<k; ++i) < 16 c *= n-i, c /= i+1; < 17 return c; < 18 } <
Deleted _lib/typical/dp.cpp version [81322e1ce041bb24]
1 // Tested: SRM 454 Lv2 < 2 template<typename T> < 3 struct DP2 < 4 { < 5 const int N1, N2; < 6 vector<T> data; < 7 DP2(int N1, int N2, const T& t = T()) < 8 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< < 9 T& operator()(int i1, int i2) < 10 { return data[ (i1*N2)+i2 ]; } < 11 void swap(DP2& rhs) < 12 { data.swap(rhs.data); } < 13 }; < 14 < 15 // Tested: Codeforces #13 C < 16 template<typename T> < 17 struct DP2x < 18 { < 19 const int N1, N2; < 20 vector<T> data; < 21 DP2x(int, int N2, const T& t = T()) < 22 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( < 23 T& operator()(int i1, int i2) < 24 { i1&=1; return data[ (i1*N2)+i2 ]; } < 25 void swap(DP2x& rhs) < 26 { data.swap(rhs.data); } < 27 }; < 28 < 29 // Tested: SRM 452 Lv3 < 30 template<typename T> < 31 struct DP3 < 32 { < 33 int N1, N2, N3; < 34 vector<T> data; < 35 DP3(int N1, int N2, int N3, const T& t = T()) < 36 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() < 37 T& operator()(int i1, int i2, int i3) < 38 { return data[ ((i1*N2)+i2)*N3+i3 ]; } < 39 void swap(DP3& rhs) < 40 { data.swap(rhs.data); } < 41 }; < 42 < 43 // Tested: SRM 468 Lv2 < 44 template<typename T> < 45 struct DP3x < 46 { < 47 int N1, N2, N3; < 48 vector<T> data; < 49 DP3x(int, int N2, int N3, const T& t = T()) < 50 : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()* < 51 T& operator()(int i1, int i2, int i3) < 52 { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } < 53 void swap(DP3x& rhs) < 54 { data.swap(rhs.data); } < 55 }; < 56 < 57 // Not Tested < 58 template<typename T> < 59 struct DP4 < 60 { < 61 int N1, N2, N3, N4; < 62 vector<T> data; < 63 DP4(int N1, int N2, int N3, int N4, const T& t = T()) < 64 : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert( < 65 T& operator()(int i1, int i2, int i3, int i4) < 66 { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } < 67 void swap(DP4& rhs) < 68 { data.swap(rhs.data); } < 69 }; < 70 < 71 // Not Tested < 72 template<typename T> < 73 struct DP4x < 74 { < 75 int N1, N2, N3, N4; < 76 vector<T> data; < 77 DP4x(int, int N2, int N3, int N4, const T& t = T()) < 78 : N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(d < 79 T& operator()(int i1, int i2, int i3, int i4) < 80 { i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } < 81 void swap(DP4x& rhs) < 82 { data.swap(rhs.data); } < 83 }; < 84 < 85 < 86 // Tested: SRM 351 Lv2 < 87 template<typename T> < 88 struct DP5 < 89 { < 90 int N1, N2, N3, N4, N5; < 91 vector<T> data; < 92 DP5(int N1, int N2, int N3, int N4, int N5, const T& t = T()) < 93 : N1(N1), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t < 94 T& operator()(int i1, int i2, int i3, int i4, int i5) < 95 { return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; } < 96 void swap(DP5& rhs) < 97 { data.swap(rhs.data); } < 98 }; < 99 < 100 // Not Tested < 101 template<typename T> < 102 struct DP5x < 103 { < 104 int N1, N2, N3, N4, N5; < 105 vector<T> data; < 106 DP5x(int, int N2, int N3, int N4, int N5, const T& t = T()) < 107 : N1(2), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t) < 108 T& operator()(int i1, int i2, int i3, int i4, int i5) < 109 { i1&=1; return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; } < 110 void swap(DP5x& rhs) < 111 { data.swap(rhs.data); } < 112 }; <
Deleted _lib/typical/idGen.cpp version [01a2602f05b036ac]
1 //------------------------------------------------------------- < 2 // ID Assignment < 3 // < 4 // Verified by < 5 // - ACM/ICPC Tokyo 2010 A < 6 // - SRM 491 Div1 LV3 < 7 //------------------------------------------------------------- < 8 < 9 template<typename T> < 10 class IdGen < 11 { < 12 map<T, int> v2id_; < 13 vector<T> id2v_; < 14 public: < 15 int v2id(const T& v) { < 16 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } < 17 return v2id_[v]; < 18 } < 19 const T& id2v(int i) const { return id2v_[i]; } < 20 int size() const { return id2v_.size(); } < 21 }; <
Deleted _lib/typical/inMap.cpp version [a5a448928ab96673]
Deleted _lib/typical/maxRectArea.cpp version [73000b9fbf0fd9f6]
1 //------------------------------------------------------------- < 2 // h[] : list of heights < 3 // i-th rectangle is located at (i,0)--(i+1,h[i]) < 4 // < 5 // calculate the area of maximum sub-rectangle < 6 // < 7 // Verified by < 8 // - SRM 337 Div1 LV2 < 9 //------------------------------------------------------------- < 10 < 11 // solve < 12 vector<int> left(n); < 13 { < 14 map<LL, int> h; h[-1] = -1; < 15 for(int i=0; i<n; ++i) { < 16 // position of the highest building < R[i] < 17 map<LL,int>::iterator it = h.lower_bound(R[i]); < 18 left[i] = (--it)->second+1; < 19 h.erase( ++it, h.end() ); < 20 h[ R[i] ] = i; < 21 } < 22 } < 23 vector<int> right(n); < 24 { < 25 map<LL, int> h; h[-1] = n; < 26 for(int i=n-1; i>=0; --i) { < 27 // position of the highest building < R[i] < 28 map<LL,int>::iterator it = h.lower_bound(R[i]); < 29 right[i] = (--it)->second-1; < 30 h.erase( ++it, h.end() ); < 31 h[ R[i] ] = i; < 32 } < 33 } < 34 LL ans = 0; < 35 for(int i=0; i<n; ++i) { < 36 LL area = R[i] * (right[i] - left[i] + 1); < 37 ans = max(ans, area); < 38 } < 39 return ans; <
Deleted _lib/typical/setCover.cpp version [3071774087420287]
1 < 2 //------------------------------------------------------------- < 3 // (Minimum) Set Cover < 4 // NP-complete < 5 // < 6 // Consider using SetCoverEasy, when mask is downward closed. < 7 // < 8 // Verified by < 9 // - SRM345 Div1 LV3 < 10 //------------------------------------------------------------- < 11 < 12 LL next_combination(LL p) < 13 { < 14 LL lsb = p & -p; < 15 LL rem = p + lsb; < 16 LL rit = rem & ~p; < 17 return rem|(((rit/lsb)>>1)-1); < 18 } < 19 < 20 // Is it possible to cover the goal by at most k elements from mask? < 21 // Assumption: goal \subseteq \bigcup mask < 22 bool canCover( LL goal, set<LL>& mask, int k ) < 23 { < 24 // optimizer < 25 for(bool update=true; update; ) { < 26 update = false; < 27 < 28 // if *it \subseteq *jt for some jt, then we NEVER use it < 29 // if *it is the only mask covering some city, we ALWAYS use it < 30 for(set<LL>::iterator it=mask.begin(); it!=mask.end(); ) { < 31 bool isSubset = false; < 32 LL onlyByMe = *it & goal; < 33 for(set<LL>::iterator jt=mask.begin(); jt!=mask.end(); + < 34 if( it!=jt ) { < 35 onlyByMe &= ~*jt; < 36 isSubset |= (*it & *jt & goal) == (*it & < 37 } < 38 < 39 update |= isSubset | !!onlyByMe; < 40 < 41 if( isSubset ) < 42 mask.erase(it++); < 43 else if( onlyByMe ) { < 44 if( --k < 0 ) < 45 return false; < 46 goal &= ~*it; < 47 mask.erase(it++); < 48 } < 49 else < 50 ++it; < 51 } < 52 < 53 if( mask.size()<=k || goal==0 ) < 54 return true; < 55 } < 56 < 57 // exhaustive search < 58 vector<LL> ms(mask.begin(), mask.end()); < 59 for(LL i=(1LL<<k)-1; i<(1LL<<ms.size()); i=next_combination(i)) < 60 { < 61 LL gg = goal; < 62 for(LL j=0; (1LL<<j)<=i; ++j) < 63 if( i & (1<<j) ) < 64 gg &= ~ms[j]; < 65 if( gg == 0 ) < 66 return true; < 67 } < 68 return false; < 69 } <
Deleted _lib/typical/setCoverEasy.cpp version [d2930c13625ebb92]
1 < 2 //------------------------------------------------------------- < 3 // (Minimum) Set Cover < 4 // NP-complete < 5 // < 6 // Assumption: "mask" must be downward closerd, < 7 // i.e., X subset Y & Y in mask => X in mask < 8 // < 9 // Verified by < 10 // - Google Code Jam 09 Round2 C < 11 // (The "Only" part never tested, in the test cases of < 12 // the problem, that optimization had never used. < 13 // Be careful to use that; to be on the safer side, < 14 // consider using the <true,false> mode.) < 15 //------------------------------------------------------------- < 16 < 17 int minCover_exhaustive( int goal, const set<int>& mask ) < 18 { < 19 typedef int STATE; < 20 < 21 vector<STATE> Q( 1, 0 ); < 22 set<STATE> visited; < 23 for(int step=0; step<=mask.size(); ++step) < 24 { < 25 vector<STATE> Q2; < 26 for(int i=0; i<Q.size(); ++i) < 27 { < 28 STATE s = Q[i]; < 29 if( s == goal ) < 30 return step; < 31 for(set<int>::const_iterator it=mask.begin(); it!=mask.e < 32 if( !visited.count( s|*it ) ) < 33 { < 34 visited.insert( s|*it ); < 35 Q2.push_back( s|*it ); < 36 } < 37 } < 38 Q.swap(Q2); < 39 } < 40 return -1; < 41 } < 42 < 43 template<bool Subs, bool Only> < 44 int minCover( int goal, set<int> mask ) < 45 { < 46 if( Subs ) < 47 for(set<int>::iterator it=mask.begin(); it!=mask.end(); ) < 48 { < 49 bool needed = true; < 50 for(int m=1; m<=goal; m<<=1) < 51 if( (goal&m) && !(*it&m) && mask.count(*it|m)) < 52 {needed = false; break;} < 53 < 54 if( needed ) < 55 ++it; < 56 else < 57 mask.erase(it++); < 58 } < 59 < 60 if( Only ) < 61 for(set<int>::iterator it=mask.begin(); it!=mask.end(); ) < 62 { < 63 int onlyByMe = goal & *it; < 64 for(set<int>::iterator jt=mask.begin(); jt!=mask.end(); < 65 onlyByMe &= ~*jt; < 66 < 67 if( !onlyByMe ) < 68 ++it; < 69 else < 70 mask.erase(it++), goal &= ~onlyByMe; < 71 } < 72 < 73 return minCover_exhaustive(goal, mask); < 74 } <
Deleted _lib/typical/ternery.cpp version [c1b48b3999a9f65a]
1 // ternery search (for shita-ni-totsu) < 2 { < 3 double x = ~min~; < 4 double w = ~max~; < 5 for(int i=0; i<~iteration~; ++i) // or, while( w-x > ~eps~ ) be careful < 6 { < 7 double y = 2*x/3 + w/3; < 8 double z = x/3 + 2*w/3; < 9 double fx = f(x); < 10 double fy = f(y); < 11 double fz = f(z); < 12 double fw = f(w); < 13 if( fx < fy ) w = y; < 14 else if( fz > fw ) x = z; < 15 else if( fy < fz ) w = z; < 16 else x = y; < 17 } < 18 } <
Deleted _lib/typical/unionfind.cpp version [734bdff2cfc3cb9d]
1 //------------------------------------------------------------- < 2 // Union-Find < 3 // Balancing + Path-Compression : O(invAckermann) < 4 // < 5 // Verified by < 6 // - SRM Member Pilot 2 Div1 LV2 < 7 //------------------------------------------------------------- < 8 < 9 struct UnionFind < 10 { < 11 vector<int> uf, sz; < 12 int nc; < 13 < 14 UnionFind(int N): uf(N), sz(N,1), nc(N) < 15 { for(int i=0; i<N; ++i) uf[i] = i; } < 16 int size() < 17 { return nc; } < 18 int Find(int a) < 19 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } < 20 bool Union(int a, int b) < 21 { < 22 a = Find(a); < 23 b = Find(b); < 24 if( a != b ) < 25 { < 26 if( sz[a] >= sz[b] ) swap(a, b); < 27 uf[a] = b; < 28 sz[b] += sz[a]; < 29 --nc; < 30 } < 31 return (a!=b); < 32 } < 33 }; <
Name change from from _lib/dataStructure/fenwickTree.cpp to lib/dataStructure/fenwickTree.cpp.
Name change from from _lib/dataStructure/rmq.cpp to lib/dataStructure/rmq.cpp.
Name change from from _lib/doc/hitori-sharp.pdf to lib/doc/hitori-sharp.pdf.
cannot compute difference between binary files
Name change from from _lib/doc/lb_ub.txt to lib/doc/lb_ub.txt.
Name change from from _lib/doc/nim.txt to lib/doc/nim.txt.
Name change from from _lib/gcj/!gcj-smpl.aml to lib/gcj/!gcj-smpl.aml.
Name change from from _lib/gcj/!gcj-smpl.as to lib/gcj/!gcj-smpl.as.
Name change from from _lib/gcj/!gcj-smpl.bl to lib/gcj/!gcj-smpl.bl.
Name change from from _lib/gcj/!gcj-smpl.cl to lib/gcj/!gcj-smpl.cl.
Name change from from _lib/gcj/!gcj-smpl.cs to lib/gcj/!gcj-smpl.cs.
Name change from from _lib/gcj/!gcj-smpl.vbs to lib/gcj/!gcj-smpl.vbs.
Name change from from _lib/gcj/!gcj-tmpl.cpp to lib/gcj/!gcj-tmpl.cpp.
Name change from from _lib/gcj/!gcj-tmpl.java to lib/gcj/!gcj-tmpl.java.
Name change from from _lib/gcj/!gcj-tmpl.lua to lib/gcj/!gcj-tmpl.lua.
Name change from from _lib/gcj/!gcj-tmpl.py to lib/gcj/!gcj-tmpl.py.
Name change from from _lib/geo/area.cpp to lib/geo/area.cpp.
Name change from from _lib/geo/ccw.cpp to lib/geo/ccw.cpp.
Name change from from _lib/geo/circle_3pt.cpp to lib/geo/circle_3pt.cpp.
Name change from from _lib/geo/convexHull.cpp to lib/geo/convexHull.cpp.
Name change from from _lib/geo/convexHull_old.cpp to lib/geo/convexHull_old.cpp.
Name change from from _lib/geo/pt_in_poly.cpp to lib/geo/pt_in_poly.cpp.
Name change from from _lib/graph/__goldberg.cpp to lib/graph/__goldberg.cpp.
Name change from from _lib/graph/biMatch.cpp to lib/graph/biMatch.cpp.
Name change from from _lib/graph/isGraphical.cpp to lib/graph/isGraphical.cpp.
Name change from from _lib/graph/maxFlow.cpp to lib/graph/maxFlow.cpp.
Name change from from _lib/graph/mincostFlow.cpp to lib/graph/mincostFlow.cpp.
Name change from from _lib/graph/undAllPairMinCut.cpp to lib/graph/undAllPairMinCut.cpp.
Name change from from _lib/graph/undMinCut.cpp to lib/graph/undMinCut.cpp.
Name change from from _lib/numeric/bigintFake.cpp to lib/numeric/bigintFake.cpp.
Name change from from _lib/numeric/erathos.cpp to lib/numeric/erathos.cpp.
Name change from from _lib/numeric/fft.cpp to lib/numeric/fft.cpp.
Name change from from _lib/numeric/gcd_lcm.cpp to lib/numeric/gcd_lcm.cpp.
Name change from from _lib/numeric/linearEq.cpp to lib/numeric/linearEq.cpp.
Name change from from _lib/numeric/linearEq2.cpp to lib/numeric/linearEq2.cpp.
Name change from from _lib/numeric/matrix.cpp to lib/numeric/matrix.cpp.
Name change from from _lib/numeric/mebius.cpp to lib/numeric/mebius.cpp.
Name change from from _lib/numeric/modArith.cpp to lib/numeric/modArith.cpp.
Name change from from _lib/numeric/modArithOld.cpp to lib/numeric/modArithOld.cpp.
Name change from from _lib/numeric/nextComb.cpp to lib/numeric/nextComb.cpp.
Name change from from _lib/numeric/sternBrocot.cpp to lib/numeric/sternBrocot.cpp.
Name change from from _lib/typical/amap.cpp to lib/typical/amap.cpp.
Name change from from _lib/typical/bfs.cpp to lib/typical/bfs.cpp.
Name change from from _lib/typical/bitop.cpp to lib/typical/bitop.cpp.
Name change from from _lib/typical/comb.cpp to lib/typical/comb.cpp.
Name change from from _lib/typical/dp.cpp to lib/typical/dp.cpp.
Name change from from _lib/typical/idGen.cpp to lib/typical/idGen.cpp.
Name change from from _lib/typical/inMap.cpp to lib/typical/inMap.cpp.
Name change from from _lib/typical/maxRectArea.cpp to lib/typical/maxRectArea.cpp.
Name change from from _lib/typical/setCover.cpp to lib/typical/setCover.cpp.
Name change from from _lib/typical/setCoverEasy.cpp to lib/typical/setCoverEasy.cpp.
Name change from from _lib/typical/ternery.cpp to lib/typical/ternery.cpp.
Name change from from _lib/typical/unionfind.cpp to lib/typical/unionfind.cpp.