Submission #212951

# Submission time Handle Problem Language Result Execution time Memory
212951 2020-03-24T15:19:43 Z ryansee Stray Cat (JOI20_stray) C++14
20 / 100
92 ms 16384 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);
				}
			}
		};
		trav(t,adj[0]) dfs(t,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 64 ms 15220 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 47 ms 14592 KB Output is correct
4 Correct 81 ms 16384 KB Output is correct
5 Correct 78 ms 16380 KB Output is correct
6 Correct 59 ms 14964 KB Output is correct
7 Correct 64 ms 15064 KB Output is correct
8 Correct 78 ms 15796 KB Output is correct
9 Correct 92 ms 15780 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 64 ms 15220 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 47 ms 14592 KB Output is correct
4 Correct 81 ms 16384 KB Output is correct
5 Correct 78 ms 16380 KB Output is correct
6 Correct 59 ms 14964 KB Output is correct
7 Correct 64 ms 15064 KB Output is correct
8 Correct 78 ms 15796 KB Output is correct
9 Correct 92 ms 15780 KB Output is correct
10 Correct 66 ms 13080 KB Output is correct
11 Correct 55 ms 13176 KB Output is correct
12 Correct 60 ms 13048 KB Output is correct
13 Correct 55 ms 13124 KB Output is correct
14 Correct 53 ms 13168 KB Output is correct
15 Correct 63 ms 13664 KB Output is correct
16 Correct 66 ms 15872 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 59 ms 12804 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 49 ms 12396 KB Output is correct
4 Correct 81 ms 14192 KB Output is correct
5 Correct 71 ms 14252 KB Output is correct
6 Correct 63 ms 12796 KB Output is correct
7 Correct 62 ms 12796 KB Output is correct
8 Correct 68 ms 13440 KB Output is correct
9 Correct 67 ms 13572 KB Output is correct
10 Correct 60 ms 13284 KB Output is correct
11 Correct 69 ms 13232 KB Output is correct
12 Correct 68 ms 13240 KB Output is correct
13 Correct 59 ms 13140 KB Output is correct
14 Correct 75 ms 13556 KB Output is correct
15 Correct 76 ms 13564 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 59 ms 12804 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 49 ms 12396 KB Output is correct
4 Correct 81 ms 14192 KB Output is correct
5 Correct 71 ms 14252 KB Output is correct
6 Correct 63 ms 12796 KB Output is correct
7 Correct 62 ms 12796 KB Output is correct
8 Correct 68 ms 13440 KB Output is correct
9 Correct 67 ms 13572 KB Output is correct
10 Correct 60 ms 13284 KB Output is correct
11 Correct 69 ms 13232 KB Output is correct
12 Correct 68 ms 13240 KB Output is correct
13 Correct 59 ms 13140 KB Output is correct
14 Correct 75 ms 13556 KB Output is correct
15 Correct 76 ms 13564 KB Output is correct
16 Correct 51 ms 11128 KB Output is correct
17 Correct 53 ms 11156 KB Output is correct
18 Correct 67 ms 11252 KB Output is correct
19 Correct 64 ms 11232 KB Output is correct
20 Correct 66 ms 11632 KB Output is correct
21 Correct 62 ms 11444 KB Output is correct
22 Correct 76 ms 13668 KB Output is correct
23 Correct 51 ms 11240 KB Output is correct
24 Correct 56 ms 11256 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 11 ms 1792 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 10 ms 1792 KB Output is correct
5 Correct 11 ms 1792 KB Output is correct
6 Correct 11 ms 1888 KB Output is correct
7 Correct 11 ms 1792 KB Output is correct
8 Correct 10 ms 1792 KB Output is correct
9 Correct 12 ms 1888 KB Output is correct
10 Correct 10 ms 1792 KB Output is correct
11 Correct 11 ms 2048 KB Output is correct
12 Correct 10 ms 1792 KB Output is correct
13 Correct 10 ms 1792 KB Output is correct
14 Correct 10 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 11 ms 1792 KB Output is correct
18 Correct 11 ms 1792 KB Output is correct
19 Correct 11 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 11 ms 1792 KB Output is correct
23 Correct 10 ms 1792 KB Output is correct
24 Correct 11 ms 1792 KB Output is correct
25 Correct 12 ms 1632 KB Output is correct
26 Correct 10 ms 1792 KB Output is correct
27 Correct 10 ms 1792 KB Output is correct
28 Correct 10 ms 1792 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 53 ms 11012 KB Output is correct
2 Correct 66 ms 13324 KB Output is correct
3 Correct 9 ms 1536 KB Output is correct
4 Correct 52 ms 11088 KB Output is correct
5 Correct 74 ms 16124 KB Output is correct
6 Correct 75 ms 16128 KB Output is correct
7 Incorrect 62 ms 15224 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 62 ms 11004 KB Output is correct
2 Correct 64 ms 13160 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 44 ms 11008 KB Output is correct
5 Correct 70 ms 16132 KB Output is correct
6 Correct 85 ms 16124 KB Output is correct
7 Incorrect 57 ms 15220 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -