Artifact 3bd5d04ce69009dd2efded61acb77854ab3ca58d

• File SRM/TCO17-3A-U/1A.cpp
  • 2017-08-19 11:17:59 - part of checkin [272cda822f] on branch trunk - tco17a3 (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

int gcd(int a, int b)
{
	while (a)
		swap(a, b %= a);
	return b;
}

bool is_coprime(int a, int b)
{
	return gcd(a, b) == 1;
}

class CoprimeMatrix { public:
	vector<bool> is_p;
	vector<int> primes;

	string isPossible(vector <string> coprime)
	{
		// eratos
		if (is_p.empty()) {
			is_p.assign(60, true);
			is_p[0] = is_p[1] = false;
			for (int p = 2; p < is_p.size(); ++p) if (is_p[p]) {
				primes.push_back(p);
				for (int q = p + p; q < is_p.size(); q += p)
					is_p[q] = false;
			}
		}

		return solve(coprime) ? "Possible" : "Impossible";
	}

	bool solve(const vector<string>& coprime)
	{
		const int N = coprime.size();

		// sanity
		for (int i = 0; i < N; ++i)
		for (int k = 0; k < N; ++k)
			if (coprime[i][k] != coprime[k][i])
				return false;

		// trivial case
		for (int i = 0; i < N; ++i)
		for (int k = 0; k < N; ++k)
			if (is_coprime(1 + i, 1 + k) != (coprime[i][k] == 'Y'))
				goto nontrivial;
		return true;

	nontrivial:
		for (int i = 0; i < N; ++i)
			if(coprime[i][i]=='Y')
				return false;

		vector<vector<bool>> cos;
		for (int off = 0; off < N; ++off) {
			vector<bool> co;
			for (int t = 0; t + off < N; ++t)
				co.push_back(coprime[off][off + t] == 'Y');

			// x+off coprime with k in 0,1,2,,,,co.size()-1 iff co[k]

			if (!can(co))
				return false;
			cos.push_back(co);
		}

		for (int p = 2; p < N; ++p) if (is_p[p]) {
			int last = -1;
			for(int o=0; o<cos.size() && cos[o].size()>p; ++o)
				if (cos[o][p] == false) {
					if (last!=-1 && (o-last)!=p)
						return false;
					last = o;
				}
				else {
					if (o - last >= p)
						return false;
				}
		}

		return true;
	}

	bool can(const vector<bool>& co)
	{
		// Can there be a positive n such that coprime(n,i) == co[i] ?
		vector<int> prime_factors;
		for (int p = 2; p < co.size(); ++p)
			if (is_p[p] && !co[p])
				prime_factors.push_back(p);

		for (int k = 0; k < co.size(); ++k)
			if (is_coprimev(k, prime_factors) != co[k]) {
				prime_factors.push_back(primes.back());
				for (int k = 0; k < co.size(); ++k)
					if (is_coprimev(k, prime_factors) != co[k])
						return false;
				return true;
			}
		return true;
	}

	bool is_coprimev(int k, const vector<int>& pfs)
	{
		for (int p : pfs)
			if (k%p == 0)
				return false;
		return true;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, CoprimeMatrix().isPossible(coprime));}
int main(){

CASE(0)
	string coprime_[] = {"NYNYN",
 "YNYYN",
 "NYNYN",
 "YYYNY",
 "NNNYN"};
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Possible"; 
END
CASE(1)
	string coprime_[] = {"NY",
 "NN"};
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Impossible"; 
END
CASE(2)
	string coprime_[] = {"NYYYYN",
 "YNYNNN",
 "YYNYYY",
 "YNYNYN",
 "YNYYNY",
 "NNYNYN"};
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Possible"; 
END
CASE(3)
	string coprime_[] = {"NN",
 "NN"};
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Impossible"; 
END
CASE(4)
// both x and x+1 and x+2 are coprime with 2
	string coprime_[] = 
{
	"NYYY",
	"YNYY",
	"YYNY",
	"YYYN",
};
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Impossible"; 
END
CASE(5)
// x+1 == 1
string coprime_[] = { "NY", "YY" };
	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_)); 
	string _ = "Impossible"; 
END
CASE(6)
string coprime_[] = { "Y" };
vector <string> coprime(coprime_, coprime_ + sizeof(coprime_) / sizeof(*coprime_));
string _ = "Possible";
END
}
// END CUT HERE