oj.uz

답안 #776579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776579 2023-07-08T04:25:49 Z maomao90 Fish (IOI08_fish) C++17
16 / 100
 3000 ms 5704 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);
	}
	ans = SZ(st);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 340 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 372 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 729 ms 2272 KB Output is correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3052 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 4104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3075 ms 5616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 4172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 3440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3066 ms 5704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3058 ms 5684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 4112 KB Output isn't correct
2 Halted 0 ms 0 KB -