oj.uz

Submission #776578

# Submission time Handle Problem Language Result Execution time Memory
776578 2023-07-08T04:25:03 Z maomao90 Fish (IOI08_fish) C++17
4 / 100
 3000 ms 4220 KB 
#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];
int ans;
//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, mxid = -1;
		//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;
			mxid = i;
			//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;
		}
		REP (i, mxid + 1, n) {
			if (la[i].SE == la[mxid].SE) {
				bad = 1;
				break;
			}
		}
		if (bad) {
			continue;
		}
		int badl = -INF;
		REP (i, mxid + 1, n) {
			if (done[la[i].SE]) {
				badl = la[i].FI;
				break;
			}
		}
		int gdl = mx;
		REP (i, 0, mxid) {
			if (msk >> i & 1) {
				continue;
			}
			if (la[i].SE == la[mxid].SE) {
				gdl = la[i].FI;
				break;
			}
		}
		RREP (i, mxid - 1, 0) {
			if (msk >> i & 1 ^ 1) {
				continue;
			}
			if (la[i].SE == la[mxid].SE) {
				mxto(gdl, la[i].FI);
				break;
			}
		}
		if (gdl * 2 <= badl) {
			continue;
		}
		ans++;
		/*
		sort(ALL(v));
		st.insert(v);
		*/
	}
	cout << ans % m << '\n';
	return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 1812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 2588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 3728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 3444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 3968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 3908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 4220 KB Output isn't correct
2 Halted 0 ms 0 KB -