Skip to content

Instantly share code, notes, and snippets.

@lychees

lychees/250.cpp

Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lychees/369d5ead82bbb3253e3d to your computer and use it in GitHub Desktop.
Save lychees/369d5ead82bbb3253e3d to your computer and use it in GitHub Desktop.
Download ZIP
SRM 622
Raw
250.cpp
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define REP(I, N) for (int I=0;I<int(N);++I)
const int N = 60;
int c[N][N], d[N][N], d0[N][N];
template<class T> inline T& checkMin(T &a,const T b){if (b<a) a=b;return a;}
class BuildingRoutes {
public:
int build(vector <string> dist, int T) {
int n = dist.size(); REP(i, n) REP(j, n) d[i][j] = d0[i][j] = dist[i][j] - '0';
REP(k, n) REP(i, n) REP(j, n)
checkMin(d[i][j], d[i][k] + d[k][j]);
memset(c, 0, sizeof(c)); REP(i, n) REP(j, n){
REP(a, n) REP(b, n) if (d[a][b] == d[a][i] + d0[i][j] + d[j][b]){
++c[i][j];
}
}
int res = 0; REP(i, n) REP(j, n) if (c[i][j] >= T) res += d0[i][j];
return res;
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (expected == received) {
verdict = "PASSED";
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string dist[] = {"011",
"101",
"110"};
int T = 1;
int expected__ = 6;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string dist[] = {"033",
"309",
"390"};
int T = 1;
int expected__ = 12;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string dist[] = {
"0111",
"1019",
"1101",
"1110"};
int T = 2;
int expected__ = 5;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string dist[] = {"0178995412340",
"1014758312345",
"6501547912345",
"5560139812345",
"7659013412345",
"5793901512345",
"1234560112345",
"6864764012345",
"6864764101345",
"6864764110145",
"6864764113015",
"6864764113101",
"9864764113110"};
int T = 1;
int expected__ = 40;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 4: {
string dist[] = ;
int T = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 5: {
string dist[] = ;
int T = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
string dist[] = ;
int T = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = BuildingRoutes().build(vector <string>(dist, dist + (sizeof dist / sizeof dist[0])), T);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
Raw
500.cpp
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define fi first
#define se second
const int N = 59;
vector<pair<int, int>> adj[N];
int n, D, res;
int dfs(int u = 0){
vector<int> chd; ECH(it, adj[u]){
int v = it->fi, d = dfs(v) + it->se;
if (d > D) ++res; else chd.push_back(d);
}
sort(chd.rbegin(), chd.rend());
int i = 0; while (i+1 < chd.size()){
if (chd[i] + chd[i+1] > D) ++res, ++i;
else break;
}
return chd.size()?chd[i]:0;
}
class Ethernet {
public:
int connect(vector <int> parent, vector <int> dist, int maxDist) {
D = maxDist, n = parent.size()+1; REP(i, n) adj[i].clear();
REP(i, n-1) adj[parent[i]].push_back(make_pair(i+1, dist[i]));
res = 1, dfs();
return res;
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (expected == received) {
verdict = "PASSED";
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum) {
switch (casenum) {
case 0: {
int parent[] = {0,0,0};
int dist[] = {1,1,1};
int maxDist = 2;
int expected__ = 1;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
int parent[] = {0,0,0,0,0,0,0};
int dist[] = {1,2,3,4,5,6,7};
int maxDist = 8;
int expected__ = 4;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
int parent[] = {0,1,2,3,4,5};
int dist[] = {1,2,3,4,5,6};
int maxDist = 6;
int expected__ = 3;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
int parent[] = {0,0,0,1,1};
int dist[] = {1,1,1,1,1};
int maxDist = 2;
int expected__ = 2;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
int parent[] = {0,1,0,3,0,5,0,6,0,6,0,6,4,6,9,4,5,5,2,5,2};
int dist[] = {93,42,104,105,59,73,161,130,30,81,62,93,131,133,139,5,13,34,25,111,4};
int maxDist = 162;
int expected__ = 11;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
int parent[] = ;
int dist[] = ;
int maxDist = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
int parent[] = ;
int dist[] = ;
int maxDist = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
int parent[] = ;
int dist[] = ;
int maxDist = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = Ethernet().connect(vector <int>(parent, parent + (sizeof parent / sizeof parent[0])), vector <int>(dist, dist + (sizeof dist / sizeof dist[0])), maxDist);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
Raw
900.cpp
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(i, a, b) for (int i=a;i<b;++i)
typedef long long LL;
const int MOD = int(1e9) + 7;
// <<= '2. Number Theory .,//{
namespace NT{
inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;}
inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;}
inline int dff(int a, int b){a -= b; if (a < 0) a += MOD; return a;}
inline void MUL(int &a, int b){a = (LL)a * b % MOD;}
inline int pdt(int a, int b){return (LL)a * b % MOD;}
inline int pow(int a, int b){
int c(1); while (b){
if (b&1) MUL(c, a);
MUL(a, a), b >>= 1;
}
return c;
}
} using namespace NT;//}
const int FN = 90;
bitset<FN> B[FN], BB;
LL F[FN];
void f(bitset<FN>& b, LL n){
if (n){
int t = upper_bound(F, F+FN, n)-F-1;
if ((n-F[t]+1)&1) b.flip(t);
f(b, n-F[t]); b ^= B[t]; //f(b, F[t]-1);
}
}
class FibonacciXor{
public:
int find(long long l, long long r) {
REP(i, FN) B[i].reset(); BB.reset();
F[0] = 1, F[1] = 2; FOR(i, 2, FN) F[i] = F[i-1] + F[i-2];
FOR(i, 1, FN) f(B[i], F[i]-1);
f(BB, r), f(BB, l-1); int res = 0;
REP(i, FN) if (BB[i]) INC(res, pow(2, i));
return res;
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (expected == received) {
verdict = "PASSED";
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum) {
switch (casenum) {
case 0: {
long long A = 1;
long long B = 2;
int expected__ = 3;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
long long A = 3;
long long B = 10;
int expected__ = 25;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
long long A = 1;
long long B = 1000000000000000LL;
int expected__ = 780431495;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 3: {
long long A = 32132132134567;
long long B = 1000000000000000LL;
int expected__ = 160469768;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}
/* case 4: {
long long A = ;
long long B = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 5: {
long long A = ;
long long B = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = FibonacciXor().find(A, B);
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment