Submission #212953

# Submission time Handle Problem Language Result Execution time Memory
212953 2020-03-24T15:23:26 Z ryansee Stray Cat (JOI20_stray) C++14
20 / 100
95 ms 16444 KB
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
 
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
 
namespace {
 
int FunctionExample(int i, int A) {
  return i % A;
}
 
}  // namespace
 
std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
	vi X(M);
    vi adj[20000];
	F0R(i,M) {
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
	}
	if (A >= 3) {
		vi dist(N,MOD);
		queue<int> q; 
		auto ad = [&](int a, int b) {
			if (dist[a] != MOD) return;
			dist[a] = b; q.push(a);
		};
		ad(0,0);
		while (sz(q)) {
			int x = q.ft; q.pop();
			trav(t,adj[x]) ad(t,dist[x]+1);
		}
		F0R(i,M) X[i] = min(dist[U[i]],dist[V[i]])%3;
	} else {
		vi col(N), depth(N);
		vi stor = {1,0,0,1,1,0};
		function<void(int,int,int)> dfs = [&](int x, int y, int b) {
			depth[x] = depth[y]+1; col[x] = stor[b]; 
			vi child; trav(t,adj[x]) if (t != y) child.pb(t);
			if (sz(child) == 1) {
				dfs(child[0],x,(b+1)%6);
			} else {
				trav(t,child) {
					if (col[x] == 1) dfs(t,x,1);
					else dfs(t,x,0);
				}
			}
		};
		dfs(0,0,0);
		F0R(i,M) {
			if (depth[U[i]] > depth[V[i]]) swap(U[i],V[i]);
			X[i] = col[V[i]];
			//dbg("HUH",V[i],X[i]);
		}
		//dbg(col);
	}
	dbg(X);
	return X;
}
#include "Catherine.h"
#include <bits/stdc++.h>
 
using namespace std;
 
namespace {
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 
 
#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
 
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
 
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
 
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
 
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }
 
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifndef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif
 
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
	int A, B;
	int lst = -1, LST = -1;
	bool mode = 0;
	vi vis;
}  // namespace
 
void Init(int A, int B) {
  ::A = A;
  ::B = B;
}
 
int Move(std::vector<int> y) {
	if (A >= 3) {
		if (lst != -1) y[lst] ++;
		F0R(i,3) {
			if (!y[i] && y[(i+1)%3]) {
				lst = (i+1)%3;
				return lst;
			}
		}
		exit(5);
	}
	/*cout << mode << " " << lst << "\n";
	cout << "Y ";
	for (int i: y) cout << i << " ";
	cout << "\n";
	cout << "VIS ";
	for (int i: vis) cout << i << " ";
	cout << "\n";
	cout << "----\n";*/
	int deg = y[0]+y[1]+(lst != -1);
	if (deg != 2) mode = 1;
	if (deg > 2) {
		int cnt0 = y[0]; if (lst == 0) cnt0 ++;
		lst = cnt0 > 1;
		return y[lst] ? lst : -1;
	}
	if (deg == 1) {
		int cnt0 = y[0]; if (lst == 0) cnt0 ++;
		lst = cnt0 == 1 ? 0 : 1;
		return y[lst] ? lst : -1;
	}
	if (mode == 1) {
		F0R(i,2) if (y[i]) return lst = i;
		exit(5);
	}
	if (lst == -1) {
		F0R(i,2) F0R(j,y[i]) vis.pb(i);
		if (y[1]) { return lst = 1; }
		return lst = 0;
	}
	F0R(i,2) if (y[i]) vis.pb(i);
	if (sz(vis) == 5) {
		mode = 1;
		int ok = MOD;
		if (vis[0] == 0 && vis[1] == 0) {
			if (vis == vi{0,0,1,1,0}) ok = 1;
			else ok = 0;
		} else if (vis[0] == 0 && vis[1] == 1) {
			if (vis == vi{0,1,1,0,1}) ok = 1;
			if (vis == vi{0,1,1,0,0}) ok = 0;
			if (vis == vi{0,1,0,0,1}) ok = 1;
			if (vis == vi{0,1,0,1,1}) ok = 0;
		} else {
			if (vis == vi{1,1,0,1,0}) ok = 1;
			else ok = 0;
		}
		assert(ok != MOD);
		if (!ok) return -1;
	}
	F0R(i,2) if (y[i]) return lst = i;
	exit(5);
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:190:8: warning: statement has no effect [-Wunused-value]
  dbg(X);
        ^
Anthony.cpp: In function 'void setIn(std::__cxx11::string)':
Anthony.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Anthony.cpp: In function 'void setOut(std::__cxx11::string)':
Anthony.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Anthony.cpp: At global scope:
Anthony.cpp:140:5: warning: 'int {anonymous}::FunctionExample(int, int)' defined but not used [-Wunused-function]
 int FunctionExample(int i, int A) {
     ^~~~~~~~~~~~~~~

Catherine.cpp:141:16: warning: '{anonymous}::LST' defined but not used [-Wunused-variable]
  int lst = -1, LST = -1;
                ^~~
Catherine.cpp:130:6: warning: 'void {anonymous}::setIO(std::__cxx11::string)' defined but not used [-Wunused-function]
 void setIO(string s = "") {
      ^~~~~
Catherine.cpp:116:6: warning: 'void {anonymous}::DBG()' defined but not used [-Wunused-function]
 void DBG() { cerr << "]" << endl; }
      ^~~
Catherine.cpp:111:6: warning: 'void {anonymous}::ps()' defined but not used [-Wunused-function]
 void ps() { pr("\n"); } // print w/ spaces
      ^~
Catherine.cpp:78:12: warning: '{anonymous}::str {anonymous}::to_string(std::vector<bool>)' defined but not used [-Wunused-function]
 #define ts to_string
            ^
Catherine.cpp:85:5: note: in expansion of macro 'ts'
 str ts(vector<bool> v) { 
     ^~
Catherine.cpp:78:12: warning: '{anonymous}::str {anonymous}::to_string({anonymous}::str)' defined but not used [-Wunused-function]
 #define ts to_string
            ^
Catherine.cpp:83:5: note: in expansion of macro 'ts'
 str ts(str s) { return s; }
     ^~
Catherine.cpp:78:12: warning: '{anonymous}::str {anonymous}::to_string(char)' defined but not used [-Wunused-function]
 #define ts to_string
            ^
Catherine.cpp:82:5: note: in expansion of macro 'ts'
 str ts(char c) { str s = ""; s += c; return s; }
     ^~
Catherine.cpp:69:6: warning: 'void {anonymous}::re({anonymous}::ld&)' defined but not used [-Wunused-function]
 void re(ld& d) { str t; re(t); d = stold(t); }
      ^~
Catherine.cpp:68:6: warning: 'void {anonymous}::re({anonymous}::db&)' defined but not used [-Wunused-function]
 void re(db& d) { str t; re(t); d = stod(t); }
      ^~
Catherine.cpp:59:5: warning: 'int {anonymous}::cdiv(int, int)' defined but not used [-Wunused-function]
 int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
     ^~~~
Catherine.cpp:58:5: warning: 'int {anonymous}::bit(int)' defined but not used [-Wunused-function]
 int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
     ^~~
Catherine.cpp:57:5: warning: 'int {anonymous}::pct(int)' defined but not used [-Wunused-function]
 int pct(int x) { return __builtin_popcount(x); } 
     ^~~
# Verdict Execution time Memory Grader output
1 Correct 73 ms 15228 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 53 ms 14628 KB Output is correct
4 Correct 86 ms 16228 KB Output is correct
5 Correct 93 ms 16444 KB Output is correct
6 Correct 78 ms 15084 KB Output is correct
7 Correct 68 ms 15024 KB Output is correct
8 Correct 95 ms 15732 KB Output is correct
9 Correct 68 ms 15732 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 73 ms 15228 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 53 ms 14628 KB Output is correct
4 Correct 86 ms 16228 KB Output is correct
5 Correct 93 ms 16444 KB Output is correct
6 Correct 78 ms 15084 KB Output is correct
7 Correct 68 ms 15024 KB Output is correct
8 Correct 95 ms 15732 KB Output is correct
9 Correct 68 ms 15732 KB Output is correct
10 Correct 68 ms 12996 KB Output is correct
11 Correct 60 ms 12916 KB Output is correct
12 Correct 57 ms 13048 KB Output is correct
13 Correct 64 ms 13032 KB Output is correct
14 Correct 56 ms 13296 KB Output is correct
15 Correct 62 ms 13816 KB Output is correct
16 Correct 66 ms 15860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 62 ms 12788 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 48 ms 12504 KB Output is correct
4 Correct 76 ms 14180 KB Output is correct
5 Correct 88 ms 14176 KB Output is correct
6 Correct 55 ms 12824 KB Output is correct
7 Correct 59 ms 12796 KB Output is correct
8 Correct 63 ms 13436 KB Output is correct
9 Correct 74 ms 13540 KB Output is correct
10 Correct 61 ms 13316 KB Output is correct
11 Correct 67 ms 13172 KB Output is correct
12 Correct 56 ms 13300 KB Output is correct
13 Correct 60 ms 13272 KB Output is correct
14 Correct 72 ms 13516 KB Output is correct
15 Correct 83 ms 13428 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 62 ms 12788 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 48 ms 12504 KB Output is correct
4 Correct 76 ms 14180 KB Output is correct
5 Correct 88 ms 14176 KB Output is correct
6 Correct 55 ms 12824 KB Output is correct
7 Correct 59 ms 12796 KB Output is correct
8 Correct 63 ms 13436 KB Output is correct
9 Correct 74 ms 13540 KB Output is correct
10 Correct 61 ms 13316 KB Output is correct
11 Correct 67 ms 13172 KB Output is correct
12 Correct 56 ms 13300 KB Output is correct
13 Correct 60 ms 13272 KB Output is correct
14 Correct 72 ms 13516 KB Output is correct
15 Correct 83 ms 13428 KB Output is correct
16 Correct 51 ms 11260 KB Output is correct
17 Correct 49 ms 11216 KB Output is correct
18 Correct 56 ms 11136 KB Output is correct
19 Correct 51 ms 11196 KB Output is correct
20 Correct 62 ms 11856 KB Output is correct
21 Correct 53 ms 11512 KB Output is correct
22 Correct 62 ms 13684 KB Output is correct
23 Correct 54 ms 11260 KB Output is correct
24 Correct 51 ms 11216 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 11 ms 1488 KB Output is correct
3 Correct 10 ms 1792 KB Output is correct
4 Correct 12 ms 1792 KB Output is correct
5 Correct 12 ms 1792 KB Output is correct
6 Correct 11 ms 1792 KB Output is correct
7 Correct 13 ms 1792 KB Output is correct
8 Correct 11 ms 1792 KB Output is correct
9 Correct 11 ms 1792 KB Output is correct
10 Correct 11 ms 1792 KB Output is correct
11 Correct 12 ms 1792 KB Output is correct
12 Correct 10 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 13 ms 1792 KB Output is correct
15 Correct 11 ms 1792 KB Output is correct
16 Correct 11 ms 1792 KB Output is correct
17 Correct 12 ms 1744 KB Output is correct
18 Correct 11 ms 1792 KB Output is correct
19 Correct 10 ms 1792 KB Output is correct
20 Correct 10 ms 1792 KB Output is correct
21 Correct 10 ms 1792 KB Output is correct
22 Correct 10 ms 1792 KB Output is correct
23 Correct 11 ms 1792 KB Output is correct
24 Correct 12 ms 1792 KB Output is correct
25 Correct 12 ms 1792 KB Output is correct
26 Correct 13 ms 1792 KB Output is correct
27 Correct 12 ms 1792 KB Output is correct
28 Correct 11 ms 1792 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 77 ms 10980 KB Output is correct
2 Correct 81 ms 13180 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 48 ms 11060 KB Output is correct
5 Correct 91 ms 15992 KB Output is correct
6 Correct 78 ms 15996 KB Output is correct
7 Incorrect 60 ms 15220 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 58 ms 11012 KB Output is correct
2 Correct 62 ms 13060 KB Output is correct
3 Correct 12 ms 1640 KB Output is correct
4 Correct 65 ms 11000 KB Output is correct
5 Correct 70 ms 16000 KB Output is correct
6 Incorrect 67 ms 16200 KB Wrong Answer [6]
7 Halted 0 ms 0 KB -