Submission #211886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211886	2020-03-21T15:10:39 Z	mode149256	Poi (IOI09_poi)	C++14	100 / 100	303 ms	16248 KB

poi

/*input
5 3 2
0 0 1
1 1 0
1 0 0
1 1 0
1 1 0
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

struct ppl {
	int sum;
	int kiek;
	int id;
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, T, P;
	cin >> N >> T >> P;

	vii sk(N, vi(T));
	vi neis(T, 0);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < T; ++j)
		{
			cin >> sk[i][j];
			neis[j] += !sk[i][j];
		}
	}

	vector<ppl> people(N);

	for (int i = 0; i < N; ++i)
	{
		auto &p = people[i];
		p.id = i + 1;
		p.sum = p.kiek = 0;

		for (int j = 0; j < T; ++j)
		{
			if (sk[i][j]) {
				p.kiek++;
				p.sum += neis[j];
			}
		}
	}

	sort(people.begin(), people.end(), [](const ppl a, const ppl b) {
		return a.sum > b.sum or (a.sum == b.sum and a.kiek > b.kiek) or
		       (a.sum == b.sum and a.kiek == b.kiek and a.id < b.id);
	});

	for (int i = 0; i < N; ++i)
	{
		if (people[i].id == P) {
			printf("%d %d\n", people[i].sum, i + 1);
			break;
		}
	}
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	7 ms	512 KB	Output is correct
11	Correct	15 ms	768 KB	Output is correct
12	Correct	21 ms	1152 KB	Output is correct
13	Correct	46 ms	2688 KB	Output is correct
14	Correct	65 ms	3748 KB	Output is correct
15	Correct	110 ms	6272 KB	Output is correct
16	Correct	126 ms	6784 KB	Output is correct
17	Correct	182 ms	9856 KB	Output is correct
18	Correct	195 ms	11008 KB	Output is correct
19	Correct	258 ms	14584 KB	Output is correct
20	Correct	303 ms	16248 KB	Output is correct