Submission #776565

#	Time	Username	Problem	Language	Result	Execution time	Memory
776565		maomao90	Fish (IOI08_fish)	C++17	16 / 100	3066 ms	6120 KiB

fish

#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

int n, k, m;
ii la[MAXN];
bool done[MAXN];
set<vi> st;

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n >> k >> m;
	REP (i, 0, n) {
		cin >> la[i].FI >> la[i].SE;
	}
	sort(la, la + n);
	REP (msk, 1, 1 << n) {
		int mx = -INF, smx = -INF;
		vi v;
		REP (i, 1, k + 1) {
			done[i] = 0;
		}
		REP (i, 0, n) {
			if (msk >> i & 1 ^ 1) {
				continue;
			}
			smx = mx;
			mx = la[i].FI;
			v.pb(la[i].SE);
		}
		if (smx * 2 > mx) {
			continue;
		}
		bool bad = 0;
		REP (i, 0, n) {
			if (la[i].FI * 2 > mx) {
				break;
			}
			if (msk >> i & 1 ^ 1) {
				if (done[la[i].SE]) {
					bad = 1;
					break;
				}
				continue;
			}
			done[la[i].SE] = 1;
		}
		if (bad) {
			continue;
		}
		sort(ALL(v));
		st.insert(v);
	}
	cout << SZ(st) % m << '\n';
	return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:56:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   56 |    if (msk >> i & 1 ^ 1) {
      |        ~~~~~~~~~^~~
fish.cpp:71:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   71 |    if (msk >> i & 1 ^ 1) {
      |        ~~~~~~~~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5