Submission #17173090

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
 
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
#include <atcoder/all>
using namespace atcoder;
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
 
 
 
ll n, m, k, q, l, r, x, y, z;
const ll template_array_size = 1e6 + 1995;
int a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;
ll ans = 0;
 
bool dp[205][105];
 
void solve(int tc = 0) {
	cin >> n;
	
	ll c[2 * n] = {0};
	for (ll i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		if (a[i] != -1) {
			--a[i];
			if (c[a[i]]++ > 0) {
				cout << "No\n";
				return;
			}
		}
		if (b[i] != -1) {
			--b[i];
			if (c[b[i]]++ > 0) {
				cout << "No\n";
				return;
			}
		}
		if (a[i] != -1 && b[i] != -1 && a[i] >= b[i]) {
			cout << "No\n";
			return;
		}
	}
	
	ll cq = 0;
	vector<pair<ll, ll>> nonq;
	
	for (ll i = 0; i < n; i++) {
		if (a[i] == -1 && b[i] == -1) ++cq;
		else nonq.push_back(make_pair(a[i], b[i]));
	}
		
	memset(dp, 0, sizeof(dp));
	
	dp[0][0] = 1;
	
	for (ll i = 0; i < 2 * n; i += 2) {
		for (ll j = 0; j <= cq; j++) {
			if (dp[i][j]) {
				for (ll k = 2; k + i <= 2 * n; k += 2) {
					bool vis[k] = {0};
			
					ll cnt = 0;
					
					bool pos = 1;
					for (pair<ll, ll> x: nonq) {
						// cout << k << " " << x << '\n';
						if (x.f != -1 && x.s != -1) {
							if ((x.f >= i && x.f < i + k) ^ (x.s >= i && x.s < i + k)) {
								pos = 0;
								break;
							} else if ((x.f >= i && x.f < i + k) && (x.s >= i && x.s < i + k)) {
								if (x.s - x.f != k / 2) {
									pos = 0;
									break;
								}
								
								// cout << x << " " << vis[x.f - i] << vis[x.s - i] << endl;
								
								if (vis[x.f - i] || vis[x.s - i]) {
									pos = 0;
									break;
								}
								
								vis[x.f - i] = vis[x.s - i] = 1;
								++cnt;
							}
						} else if (x.f != -1) {
							if (x.f >= i && x.f < i + k / 2) {
								if (vis[x.f - i] || vis[x.f + k / 2 - i]) {
									pos = 0;
									break;
								}
								
								vis[x.f - i] = vis[x.f + k / 2 - i] = 1;
								++cnt;
							} else if (x.f >= i + k / 2 && x.f < i + k) {
								pos = 0;
								break;
							}
						} else if (x.s != -1) {
							if (x.s >= i + k / 2 && x.s < i + k) {
								if (vis[x.s - i] || vis[x.s - k / 2 - i]) {
									pos = 0;
									break;
								}
								
								vis[x.s - i] = vis[x.s - k / 2 - i] = 1;
								++cnt;
							} else if (x.s >= i && x.s < i + k / 2) {
								pos = 0;
								break;
							}
						}
						// cout << x << endl;
					}
					
					ll rem = j + k / 2 - cnt;
					
					// cout << i << " " << j << " " << k << " " << cnt << " " << cq << " " << rem << " " << pos << '\n';
					
					if (rem > cq) pos = 0;
					
					if (pos) {
						dp[i + k][rem] = 1;
					}
				}
			}
		}
	}
	
	cout << (dp[2 * n][cq] ? "Yes\n" : "No\n");
}
 
int main() {
	#ifdef galen_colin_local
		auto begin = std::chrono::high_resolution_clock::now();
	#endif
	
	send help
 
	#ifndef galen_colin_local
		// usaco("moop");
	#endif
	
	// usaco("cowland");
	
	// freopen("tc.cpp", "r", stdin);
 
	
	
	int tc = 1;
	// cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
	
	#ifdef galen_colin_local
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(4) << fixed;
		// cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
} 

Submission Info

Compile Error

./Main.cpp: In function ‘void solve(int)’:
./Main.cpp:53:16: warning: unused parameter ‘tc’ [-Wunused-parameter]
   53 | void solve(int tc = 0) {
      |            ~~~~^~~~~~
./Main.cpp: In function ‘void usaco(std::string)’:
./Main.cpp:29:9: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
   29 |  freopen((filename + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:30:9: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
   30 |  freopen((filename + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result