oj.uz

Submission #776567

# Submission time Handle Problem Language Result Execution time Memory
776567 2023-07-08T04:08:15 Z maomao90 Fish (IOI08_fish) C++17
16 / 100
 3000 ms 5880 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];
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, mxid + 1, n) {
			if (la[i].SE == la[mxid].SE) {
				bad = 1;
				break;
			}
		}
		if (bad) {
			continue;
		}
		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

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:81:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   81 |    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
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3046 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 2 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 37 ms 1868 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 62 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 2560 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 3062 ms 5600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 3440 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 3074 ms 5696 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 3057 ms 5880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

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