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 => x = #" ") s) 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 then "ON" else "OFF") ^ "\n") 33 - in 34 - case readLine () of 35 - | [SOME t] => List.app printOne (List.map solveOne (List.tabulate (t, parseOne))) 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":"OFF") + "\n" 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(y)); 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{return this.split(" ");}); 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].length()) ).print(); 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') /+ los 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) + 1] in 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 - firstVisitEarn[q] in 126 - let rest := R - i in 127 - ( 128 - totalEarn :+ loopEarn * (rest / loopSize), 129 - // clear 130 - firstVisitTime := make_list(N, -1), 131 - i := R - (rest mod loopSize) 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], readLine()), 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,g)); 20 - } 21 - } 22 - 23 - static long[] readLongArray() 24 - { 25 - return (from s in Console.ReadLine().Split(' ') select long.Parse(s)).ToArray(); 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, (void*)i, 0, 0) ); 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]
1 -import sys 2 - 3 -CN = int(sys.stdin.next()) 4 -for C in range(1, CN+1): 5 - print "Case #%d:"%(C), 6 - N = int(sys.stdin.next()) 7 - M = int(sys.stdin.next()) 8 - for i in range(0, M): 9 - a = map(int, sys.stdin.next().split(" ")) 10 - print a 11 - print N, M
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<double>& V ) 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]); break;} 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())/2.0; 49 - M[1][0] = +p2.real(); M[1][1] = -p3.real(); V[1] = (p3.imag()-p2.imag())/2.0; 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], p[i]) IS_RIGHT ) 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], p[i]) IS_RIGHT ) 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,blocked)) ) { 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]!=S ) 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, make_pair(u,v)) ); 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|prev[v]==-1} 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]=weight[t], weight[t]=mincut; 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]==ps_t[i]; ++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_root, t_to_root); 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.begin(); 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]
1 - static const int N = 999999; 2 - vector<bool> isp(N+1, true); 3 - vector<int> ps; 4 - for(int p=2; p<=N; ++p) 5 - if( isp[p] ) { 6 - ps.push_back(p); 7 - for(int q=p+p; q<=N; q+=p) 8 - isp[q] = false; 9 - }
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)]*polar(1.0, F*2*M_PI*i/n); 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<double>& V ) 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]); break;} 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<double>& V ) 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<LL> >& B ) 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<LL> >& B ) 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) * FAC(n-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[nn-1][kk]); 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)+...+GEO(x,e) 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[nn-1][kk]); 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)+...+GEO(x,e) 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]
1 -int bitcnt(LL x) 2 -{ 3 - int c = 0; 4 - for(; x; x>>=1) 5 - c += x&1; 6 - return c; 7 -}
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)<(1<<26)); } 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)<(1<<26)); } 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()*sizeof(T)<(1<<26)); } 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()*sizeof(T) < (1<<26)); } 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(data.size()*sizeof(T)<(1<<26)); } 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(data.size()*sizeof(T)<(1<<26)); } 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) { assert(data.size()*sizeof(T)<(1<<26)); } 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) { assert(data.size()*sizeof(T)<(1<<26)); } 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]
1 - 2 -bool inMap(int H, int W, int y, int x) 3 -{ 4 - return (0<=y && y<H && 0<=x && x<W); 5 -}
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(); ++jt) 34 - if( it!=jt ) { 35 - onlyByMe &= ~*jt; 36 - isSubset |= (*it & *jt & goal) == (*it & goal); 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.end(); ++it) 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(); ++jt) 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 for precision! 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.