Skip to content

Instantly share code, notes, and snippets.

@lychees
Last active December 20, 2015 13:39
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/6140957 to your computer and use it in GitHub Desktop.
Save lychees/6140957 to your computer and use it in GitHub Desktop.
SRM 586
/* &*#()&*#)&E*F& */
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#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=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
typedef long long LL;
typedef double DB;
typedef vector<int> VI;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
int D[N][N]; VI A[N]; string B; int n;
void parse(string s){
int p = s.find('-');
string a = s.substr(0, p), b = s.substr(p+1, SZ(s));
int d1 = a[0] - 'A', d2 = b[0] - 'A'; a.erase(0, 1), b.erase(0, 1);
istringstream iss1(a); int m1; iss1 >> m1;
istringstream iss2(b); int m2; iss2 >> m2;
int l1 = A[d1][m1], r1 = A[d1][m1+1]-1;
int l2 = A[d2][m2], r2 = A[d2][m2+1]-1;
checkMin(D[d1][d2], r2 - l1), checkMin(D[d2][d1], r1 - l2);
}
char check(){
REP_3(k, i, j, n, n, n) checkMin(D[i][j], D[i][k] + D[k][j]);
REP(i, n) if (D[i][i] < 0) return 'N';
return 'Y';
}
class History {
public:
string verifyClaims(vector <string> dynasties, vector <string> battles, vector <string> queries) {
n = SZ(dynasties); REP(i, n){
CLR(A[i]); istringstream iss(dynasties[i]);
int t; while (iss >> t) A[i].PB(t);
}
CLR(B); ECH(it, battles) B += *it;
string res; ECH(it, queries){
FLC(D, 0xe); istringstream iss(B);
string s; while (iss >> s) parse(s); parse(*it);
res += check();
}
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 string &expected, const string &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 dynasties[] = {"1 2 4",
"1 2 3"};
string battles[] = {"A1-B0"};
string queries[] = {"A0-B0",
"A0-B1",
"A1-B0",
"A1-B1"};
string expected__ = "NNYY";
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string dynasties[] = {"1000 2000 3000 10000",
"600 650 2000",
"1 1001 20001"};
string battles[] = {"B1-C0 A0-B0 A2-C1 B1-C1"};
string queries[] = {"A0-B1",
"A1-B1",
"A2-B1",
"C0-A0",
"B0-A2",
"C1-B0"};
string expected__ = "YYYYNN";
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string dynasties[] = {"1 4 5",
"10 13 17"};
string battles[] = {"A0-B0 A0-B0 B0-A0"};
string queries[] = {"A1-B0",
"A0-B1",
"A1-B1"};
string expected__ = "YYY";
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string dynasties[] = {"1 5 6",
"1 2 5"};
string battles[] = {"A0",
"-B0 A",
"1-B1"};
string queries[] = {"A0-B0",
"A1-B0",
"A0-B1",
"A1-B1"};
string expected__ = "YNYY";
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string dynasties[] = {"2294 7344","366 384 449 965 1307 1415","307 473 648 688 1097","1145 1411 1569 2606","87 188 551 598 947 998 1917 1942"}
;
string battles[] = {"A0-B4 B4-E2 B3-E2 D2-E4 A0-E4 B1-C3 A0-E3 A0-E6 D0","-E2 B2-E1 B4-E3 B4-D0 D0-E3 A0-D1 B2-C3 B1-C3 B4-E","3 D0-E1 B3-D0 B3-E2"}
;
string queries[] = {"A0-C2","E6-C2","A0-E4","B3-C1","C0-D2","B0-C1","D1-C3","C3-D0","C1-E3","D1-A0"};
string expected__ = "YNYNNYNNNY";
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
string dynasties[] = ;
string battles[] = ;
string queries[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
string dynasties[] = ;
string battles[] = ;
string queries[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
string dynasties[] = ;
string battles[] = ;
string queries[] = ;
string expected__ = ;
clock_t start__ = clock();
string received__ = History().verifyClaims(vector <string>(dynasties, dynasties + (sizeof dynasties / sizeof dynasties[0])), vector <string>(battles, battles + (sizeof battles / sizeof battles[0])), vector <string>(queries, queries + (sizeof queries / sizeof queries[0])));
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
/* &*#()&*#)&E*F& */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#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=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define fi first
#define se second
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
typedef vector<PII> VII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
class PiecewiseLinearFunction {
public:
int maximumSolutions(vector <int> Y) {
FOR(i, 1, SZ(Y)) if (Y[i] == Y[i-1]) return -1;
VII L; REP(i, SZ(Y)) Y[i] *= 2, L.PB(MP(Y[i], -1)), L.PB(MP(Y[i], +1));
FOR(i, 1, SZ(Y)) L.PB(MP(min(Y[i-1], Y[i])+1, -1)), L.PB(MP(max(Y[i-1], Y[i])-1, +1));
SRT(L); int res = 0, s = 0;
REP(i, SZ(L)) checkMax(res, s -= L[i].se);
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 Y[] = {1, 2, 3};
int expected__ = 1;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
int Y[] = {4, 4};
int expected__ = -1;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
int Y[] = {1, 4, -1, 2};
int expected__ = 3;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
int Y[] = {2, 1, 2, 1, 3, 2, 3, 2};
int expected__ = 5;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
int Y[] = {125612666, -991004227, 0, 6, 88023, -1000000000, 1000000000, -1000000000, 1000000000};
int expected__ = 6;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
int Y[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
int Y[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
int Y[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = PiecewiseLinearFunction().maximumSolutions(vector <int>(Y, Y + (sizeof Y / sizeof Y[0])));
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
/* &*#()&*#)&E*F& */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#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=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
typedef long long LL;
typedef double DB;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int N = 60, Z = 27;
int dp[N][Z][Z]; //Gray, White
class StringWeight {
public:
int getMinimum(vector <int> L) {
int n = SZ(L); FLC(dp, 0x3f), dp[0][0][26] = 0;
REP_3(i, j, k, n, 27, 27) if (dp[i][j][k] != INF){
REP_2(jj, kk, j+1, k+1){ // Black, Gray ..
if (j + kk < min(26, L[i]) || jj + kk > L[i]) continue;
int b = dp[i][j][k] + (jj-1)*jj/2 + (j-jj)*L[i];
if (jj + kk == 26) b += L[i] - 26;
REP(jjj, kk+1) checkMin(dp[i+1][j-jj+jjj][k-kk], b += jjj);
}
}
int res = INF; REP_2(i, j, Z, Z) checkMin(res, dp[n][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: {
int L[] = {1};
int expected__ = 0;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
int L[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int expected__ = 1;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
int L[] = {26, 2, 2};
int expected__ = 8;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
int L[] = {25, 25, 25, 25};
int expected__ = 1826;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
int L[] = {14, 6, 30, 2, 5, 61};
int expected__ = 1229;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
int L[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 6: {
int L[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}*/
/* case 7: {
int L[] = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = StringWeight().getMinimum(vector <int>(L, L + (sizeof L / sizeof L[0])));
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