#include <set>
#include <string>
#include <utility>
#include <vector>
#include "validate.h"

const unsigned MAX_QUALITY = 1000;
const unsigned MAX_WORD_COUNT = 10000;

struct point {
    unsigned wc_diff;
    unsigned quality;
};

// Returns -1 if lhs dominates rhs,
//         +1 if rhs dominates lhs,
//          0 otherwise.
int dominance_comparison(point const &lhs, point const &rhs) {
    if (lhs.wc_diff == rhs.wc_diff && lhs.quality == rhs.quality) {
        return 0;
    }
    if (lhs.wc_diff <= rhs.wc_diff && lhs.quality >= rhs.quality) {
        return -1;
    }
    if (lhs.wc_diff >= rhs.wc_diff && lhs.quality <= rhs.quality) {
        return +1;
    }
    return 0;
}

// Reads author's output and validates the basic constraints.
std::vector<point> read_author_output(unsigned n, unsigned required_word_count) {
    std::vector<point> points(n);

    for (unsigned line = 0; line < n; ++line) {
        unsigned word_count;
        unsigned quality;
        if (!(author_out >> word_count)) {
            wrong_answer("Line %u: could not read word count", line + 1);
        }
        if (word_count > MAX_WORD_COUNT) {
            wrong_answer("Line %u: word count %u is not in [0; %u]", line + 1, word_count, MAX_WORD_COUNT);
        }
        if (!(author_out >> quality)) {
            wrong_answer("Line %u: could not read quality", line + 1);
        }
        if (quality > MAX_QUALITY) {
            wrong_answer("Line %u: quality %u is not in [0; %u]", line + 1, quality, MAX_QUALITY);
        }
        points[line].quality = quality;
        points[line].wc_diff = word_count >= required_word_count ?
            word_count - required_word_count : required_word_count - word_count;
    }

    return points;
}

// If there are any coinciding points, it is a wrong answer
void ensure_points_are_different(std::vector<point> const &points) {
    std::set<std::pair<unsigned, unsigned>> the_set;
    for (auto pt : points) {
        auto p = std::make_pair(pt.wc_diff, pt.quality);
        if (the_set.count(p) > 0) {
            wrong_answer("Point (%u, %u) appears twice", pt.wc_diff, pt.quality);
        }
        the_set.insert(p);
    }
}

// Performs deductive sort of the given points, returns the number of comparisons.
unsigned deductive_sort(std::vector<point> const &points) {
    unsigned n = points.size();
    unsigned n_comparisons = 0;

    // Stores the current lower bound on a rank.
    // Note that if ranks[i] == rank, then the point is not yet filtered out in the current iteration.
    std::vector<unsigned> ranks(n, 0);

    // This can be made faster by a constant factor,
    // but the implementation will be more complicated,
    // so I think we just use the straightforward one.
    for (unsigned rank = 0; rank < n; ++rank) {
        for (unsigned l = 0; l < n; ++l) {
            if (ranks[l] != rank) continue;
            for (unsigned r = l + 1; r < n; ++r) {
                if (ranks[r] != rank) continue;
                int cmp = dominance_comparison(points[l], points[r]);
                ++n_comparisons;
                if (cmp < 0) {
                    ++ranks[r];
                } else if (cmp > 0) {
                    ++ranks[l];
                    break;
                }
            }
        }
    }
    return n_comparisons;
}

int main(int argc, char **argv) {
    init_io(argc, argv);

    // Read problem input
    unsigned n, required_word_count;
    if (!(judge_in >> n >> required_word_count)) {
        judge_error("Cannot read problem input");
    }

    // Read author's output
    std::vector<point> points = read_author_output(n, required_word_count);

    // Fail if there is more author's output than needed
    std::string trash;
    if (author_out >> trash) {
        wrong_answer("Trailing output");
    }

    // Check whether the points are all different
    ensure_points_are_different(points);

    // Evaluate the quality of the author's output and fail if insufficient
    unsigned n_comparisons = deductive_sort(points);
    double threshold = 1.0 / 20 * n * n * n;
    if (n_comparisons < threshold) {
        wrong_answer("Too small: n = %d, n^3/20 = %lf, comparisons = %d", n, threshold, n_comparisons);
    }

    // If not failed, accept
    accept();
}