checker for problem "transfer"

// Author: Ivan Kazmenko (gassa@mail.ru)
#include "testlib.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
#include <stdint.h>
#include <vector>

using namespace std;

struct LCG // for portability: 48-bit random numbers engine used in Java
{
    static const int64_t LCG_MULT = 0x5DEECE66DLL;
    static const int64_t LCG_ADD  =         0xBLL;
    static const int64_t LCG_MASK = (1LL << 48) - 1;

    int64_t state;

    void init (int64_t seed)
    {
        state = (seed ^ LCG_MULT) & LCG_MASK;
    }

    int next ()
    {
        state = ((state * LCG_MULT) + LCG_ADD) & LCG_MASK;
        return (int) (state >> 17);
    }

    int uniform (int range) // [0..range)
    {
        if (range <= 0)
        {
            assert (false);
        }
        if ((range & -range) == range)
        {
            return (int) ((range * 1LL * next ()) >> 31);
        }
        int limit = (0x7FFFFFFF / range) * range;
        int temp;
        do
        {
            temp = next ();
        }
        while (temp >= limit);
        return temp % range;
    }

    int uniform (int lo, int hi) // [lo..hi]
    {
        return lo + uniform (hi - lo + 1);
    }
};

struct Time
{
    int value;

    Time ()
    {
    }

    Time (int newValue)
    {
        value = newValue;
    }

    Time (const Time & other)
    {
        value = other.value;
    }

    Time operator + (const Time other) const
    {
        return Time (value + other.value);
    }

    Time operator - (const Time other) const
    {
        return Time (value - other.value);
    }

    Time & operator += (const Time other)
    {
        value += other.value;
        return *this;
    }
};

bool operator < (const Time a, const Time b)
{
    return a.value < b.value;
}

bool operator > (const Time a, const Time b)
{
    return a.value > b.value;
}

bool operator != (const Time a, const Time b)
{
    return a.value != b.value;
}

Time seconds (int value)
{
    return Time (value);
}

Time minutes (int value)
{
    return Time (value * 60);
}

Time hours (int value)
{
    return Time (value * 60 * 60);
}

struct Point
{
    int x;
    int y;

    Point ()
    {
    }

    Point (int newX, int newY)
    {
        x = newX;
        y = newY;
    }
};

bool operator < (const Point a, const Point b)
{
    if (a.x != b.x)
    {
        return a.x < b.x;
    }
    return a.y < b.y;
}

int64_t distSquared (const Point & p, const Point & q)
{
    return (q.x - p.x) * 1LL * (q.x - p.x) +
        (q.y - p.y) * 1LL * (q.y - p.y);
}

struct Query
{
    int from;
    int to;
    Time moment;

    Query ()
    {
    }

    Query (int newFrom, int newTo, Time newMoment)
    {
        from = newFrom;
        to = newTo;
        moment = newMoment;
    }
};

struct Driver
{
    int garage;
    Time momentStart;
    Time momentFinish;

    Driver ()
    {
    }

    Driver (int newGarage, Time newMomentStart, Time newMomentFinish)
    {
        garage = newGarage;
        momentStart = newMomentStart;
        momentFinish = newMomentFinish;
    }
};

enum COMMAND {NO_COMMAND, MOVE, PICK1, PICK2, DROP1, DROP2};

struct Instruction
{
    COMMAND command;
    Time moment;
    int arg1;
    int arg2;
};

struct Solution
{
    vector <vector <Instruction> > instruction;

    void read (InStream & stream)
    {
        instruction.clear ();
        while (!stream.seekEof ())
        {
            int curDriver = (int) instruction.size ();
            vector <Instruction> cur;
            string temp = stream.readLine ();

            stringstream noLine;
            noLine << "driver ";
            noLine << curDriver;
            noLine << ": no";
            if (temp == noLine.str ())
            {
                instruction.push_back (cur);
                continue;
            }

            stringstream yesLine;
            yesLine << "driver ";
            yesLine << curDriver;
            yesLine << ": yes";
            if (temp != yesLine.str ())
            {
                quitf (_pe, "expected `%s' or `%s', "
                    "found `%s'", yesLine.str ().c_str (),
                    noLine.str ().c_str (), temp.c_str ());
            }

            while (true)
            {
                int curLine = (int) cur.size () + 1;
                string line = stream.readLine ();
                if (line == "end")
                {
                    break;
                }
                stringstream buf (line);
                string command;
                buf >> command;
                int args = -1;
                Instruction instr;
                if (command == "move")
                {
                    instr.command = MOVE;
                    args = 1;
                }
                else if (command == "pick1")
                {
                    instr.command = PICK1;
                    args = 1;
                }
                else if (command == "pick2")
                {
                    instr.command = PICK2;
                    args = 2;
                }
                else if (command == "drop1")
                {
                    instr.command = DROP1;
                    args = 1;
                }
                else if (command == "drop2")
                {
                    instr.command = DROP2;
                    args = 2;
                }
                else
                {
                    quitf (_pe, "driver %d, command %d: "
                        "expected command or `end', "
                        "found `%s'", curDriver, curLine,
                        command.c_str ());
                }
                buf >> instr.moment.value;
                if (args >= 1)
                {
                    buf >> instr.arg1;
                }
                if (args >= 2)
                {
                    buf >> instr.arg2;
                }
                string temp;
                buf >> temp;
                if (temp != "")
                {
                    quitf (_pe, "driver %d, command %d: "
                        "got `%s' after arguments",
                        curDriver, curLine,
                        temp.c_str ());
                }
                cur.push_back (instr);
            }
            instruction.push_back (cur);
        }
    }
};

struct SolutionResult
{
    int64_t expenses;
    int queriesMissed;
    int q;
    int driversHired;
    int d;

    SolutionResult (int64_t newExpenses, int newQueriesMissed, int newQ,
        int newDriversHired, int newD)
    {
        expenses = newExpenses;
        queriesMissed = newQueriesMissed;
        q = newQ;
        driversHired = newDriversHired;
        d = newD;
    }
};

struct Test
{
    static const Point origin;

    LCG rnd;
    unsigned seed;
    int r, a, g, q, n, dm, d;

    vector <Point> point;
    vector <Query> query;
    vector <Driver> driver;
    vector <vector <int> > gdist;
    vector <vector <Time> > gtime;

    Point uniformFreePoint (set <Point> & visited, int r)
    {
        Point res;
        do
        {
            res.x = rnd.uniform (-r, +r);
            res.y = rnd.uniform (-r, +r);
        }
        while (distSquared (origin, res) > r * 1LL * r ||
            visited.find (res) != visited.end ());
        return res;
    }

    void addFarPoints (set <Point> & visited, int num)
    {
        int startPos = point.size ();
        for (int i = 0; i < num; i++)
        {
            vector <Point> temp;
            vector <int64_t> minDistSquared;
            int64_t maxDistSquared = -1;
            for (int j = 0; j <= i; j++)
            {
                Point curPoint = uniformFreePoint (visited, r);
                int64_t curDistSquared = r * 9LL * r;
                for (int k = 0; k < i; k++)
                {
                    curDistSquared = min (curDistSquared,
                        distSquared (point[startPos + k],
                        curPoint));
                }
                maxDistSquared = max (maxDistSquared,
                    curDistSquared);
                temp.push_back (curPoint);
                minDistSquared.push_back (curDistSquared);
            }

            int j = 0;
            while (maxDistSquared != minDistSquared[j])
            {
                j++;
                if (j > i)
                {
                    assert (false);
                }
            }
            point.push_back (temp[j]);
            visited.insert (temp[j]);
        }
    }

    Point skewFreePoint (set <Point> & visited, int r)
    {
        Point res;
        do
        {
            Point pre;
            do
            {
                pre.x = rnd.uniform (-r, +r);
                pre.y = rnd.uniform (-r, +r);
            }
            while (distSquared (origin, pre) > r * 1LL * r);

            static const int p = 1000003;
            int s = rnd.uniform (1, p);
            res = Point ((int)
                (round (pre.x * 1.0 * s / p)), (int)
                (round (pre.y * 1.0 * s / p)));
        }
        while (visited.find (res) != visited.end ());
        return res;
    }

    void generatePoints ()
    {
        point.clear ();
        point.reserve (n);
        set <Point> visited;

        addFarPoints (visited, a);

        addFarPoints (visited, g);

        for (int i = 0; i < q; i++)
        {
            Point curPoint = skewFreePoint (visited, r);
            point.push_back (curPoint);
            visited.insert (curPoint);
        }
    }

    void generateQueries ()
    {
        query.clear ();
        query.reserve (q);
        set <Time> times [a];
        int curNumber = a + g;
        while ((int) query.size () < q)
        {
            int t = rnd.uniform (0, 1);
            int atemp = rnd.uniform (1, a);
            int b = rnd.uniform (0, atemp - 1);
            Time m;
            do
            {
                m = minutes (rnd.uniform (3 * 60, 21 * 60));
            }
            while (times[b].find (m) != times[b].end ());
            times[b].insert (m);
            int w = rnd.uniform (1, 20);
            int c;
            do
            {
                c = rnd.uniform (1, w);
            }
            while ((int) query.size () + c > q);
            for (int i = 0; i < c; i++)
            {
                query.push_back (Query
                    ((t == 0) ? curNumber : b,
                    (t == 0) ? b : curNumber, m));
                curNumber++;
            }
        }
    }

    void generateDrivers ()
    {
        driver.clear ();
        driver.reserve (d);
        for (int i = 0; i < d; i++)
        {
            int gtemp = rnd.uniform (1, g);
            int h = rnd.uniform (0, gtemp - 1);
            Time m = hours (rnd.uniform (0, 12));
            driver.push_back (Driver (h + a, m, m + hours (12)));
        }
    }

    void generateMatrices ()
    {
        gdist = vector <vector <int> > (n, vector <int> (n));
        gtime = vector <vector <Time> > (n, vector <Time> (n));
        for (int u = 0; u < n; u++)
        {
            for (int v = 0; v < n; v++)
            {
                int e = (int) (ceil (sqrt (distSquared
                    (point[u], point[v]) * 1.0)));
                int t = (int) (ceil (e * 60.0 / 1000));
                gdist[u][v] = rnd.uniform (e, 2 * e);
                gtime[u][v] = seconds (rnd.uniform (t, 2 * t));
            }
        }
    }

    void generate (unsigned newSeed)
    {
        seed = newSeed;
        rnd.init (seed);

        r = rnd.uniform (10000, 50000);

        do
        {
            a = rnd.uniform (1, 5);
            g = rnd.uniform (1, 10);
            q = rnd.uniform (500, 2000);
            n = a + g + q;
        }
        while (n > 2000);

        dm = (int) (ceil (r * 1.0 * q / 100000));
        d = rnd.uniform (dm, 2 * dm);

        generatePoints ();
        generateQueries ();
        generateDrivers ();
        generateMatrices ();
    }

    void write (FILE * fout = stdout)
    {
        fprintf (fout, "%u\n", seed);
        fprintf (fout, "%d %d %d %d\n", a, g, q, d);
        for (int i = 0; i < (int) point.size (); i++)
        {
            fprintf (fout, "%d %d\n", point[i].x, point[i].y);
        }
        for (int i = 0; i < (int) query.size (); i++)
        {
            fprintf (fout, "%d %d %d\n",
                query[i].from,
                query[i].to,
                query[i].moment.value);
        }
        for (int i = 0; i < (int) driver.size (); i++)
        {
            fprintf (fout, "%d %d %d\n",
                driver[i].garage,
                driver[i].momentStart.value,
                driver[i].momentFinish.value);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                fprintf (fout, "%d%c",
                    gdist[i][j], "\n "[j + 1 < n]);
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                fprintf (fout, "%d%c",
                    gtime[i][j].value, "\n "[j + 1 < n]);
            }
        }
    }

    void read (InStream & stream)
    {
        a = stream.readInt ();
        g = stream.readInt ();
        q = stream.readInt ();
        n = a + g + q;
        d = stream.readInt ();

        point = vector <Point> (n);
        for (int i = 0; i < n; i++) // vertices
        {
            point[i].x = stream.readInt ();
            point[i].y = stream.readInt ();
        }

        query = vector <Query> (q);
        for (int i = 0; i < q; i++) // queries
        {
            query[i].from = stream.readInt ();
            query[i].to = stream.readInt ();
            query[i].moment = seconds (stream.readInt ());
        }

        driver = vector <Driver> (d);
        for (int i = 0; i < d; i++) // drivers
        {
            driver[i].garage = stream.readInt ();
            driver[i].momentStart = seconds (stream.readInt ());
            driver[i].momentFinish = seconds (stream.readInt ());
        }

        gdist = vector <vector <int> > (n, vector <int> (n));
        for (int i = 0; i < n; i++) // distances
        {
            for (int j = 0; j < n; j++)
            {
                gdist[i][j] = stream.readInt ();
            }
        }

        gtime = vector <vector <Time> > (n, vector <Time> (n));
        for (int i = 0; i < n; i++) // travel times
        {
            for (int j = 0; j < n; j++)
            {
                gtime[i][j] = seconds (stream.readInt ());
            }
        }
    }

    bool isClientFromAirport (int i) const
    {
        return query[i].from < a;
    }

    bool isClientToAirport (int i) const
    {
        return query[i].to < a;
    }

    static const int SALARY;
    static const int PENALTY;
    static const Time PICK_TIME;
    static const Time DROP_TIME;
    static const Time MAX_DRIVING_TIME;
    static const Time MAX_EXTRA_TIME;

    int64_t distanceOptimistic ()
    {
        int64_t res = 0;
        for (int i = 0; i < q; i++)
        {
            res += gdist[query[i].from][query[i].to];
        }
        return res;
    }

    int driversOptimistic ()
    {
        int64_t totalTime = 0;
        for (int i = 0; i < q; i++)
        {
            totalTime += gtime[query[i].from][query[i].to].value;
        }
        return ceil (totalTime * 1.0 / MAX_DRIVING_TIME.value);
    }

    int64_t expensesOptimistic ()
    {
        return distanceOptimistic () +
            SALARY * 1LL * driversOptimistic ();
    }

    enum CLIENT_STATE {WAITING, MOVING, DROPPED};
    static int const NA = -1;

    vector <CLIENT_STATE> clientState;
    vector <int> clientCar;

    vector <Time> driverMoment;
    vector <Time> driverTotalTime;
    vector <COMMAND> driverPreviousCommand;
    vector <int> driverPos;
    vector <pair <int, int> > driverClient;

    void pickClient (int i, int j, int k, Time moment)
    {
        if (i < 0 || q <= i)
        { // CHK_QUERY_BOUNDS
            quitf (_wa, "driver %d "
                "after %d actions: "
                "invalid client %d",
                j, k, i);
        }
        if (clientState[i] != WAITING)
        {
            quitf (_wa, "driver %d "
                "after %d actions: "
                "picking client %d "
                "who is not waiting",
                j, k, i);
        }
        if (isClientFromAirport (i) &&
            moment != query[i].moment)
        { // CHK_MOMENT_FROM_AIRPORT
            quitf (_wa, "driver %d "
                "after %d actions: "
                "picking client %d "
                "at moment %d instead "
                "of moment %d", j, k, i,
                moment.value,
                query[i].moment.value);
        }
        if (isClientToAirport (i))
        {
            Time maxDuration = PICK_TIME +
                gtime[query[i].from][query[i].to] +
                DROP_TIME + MAX_EXTRA_TIME;
            Time actualDuration = query[i].moment - moment;
            if (actualDuration > maxDuration)
            { // CHK_DURATION_TO_AIRPORT
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "picking client %d "
                    "at moment %d means "
                    "total query time %d, "
                    "but maximum allowed "
                    "time is %d", j, k, i,
                    moment.value,
                    actualDuration.value,
                    maxDuration.value);
            }
        }
        clientState[i] = MOVING;
        clientCar[i] = j;

        if (driverClient[j].first == NA)
        {
            driverClient[j].first = i;
        }
        else if (driverClient[j].second == NA)
        {
            driverClient[j].second = i;
        }
        else
        { // CHK_DRIVER_CAPACITY
            quitf (_wa, "driver %d "
                "after %d actions: "
                "picking client %d "
                "when clients %d "
                "and %d are in the car",
                j, k, i,
                driverClient[j].first,
                driverClient[j].second);
        }

        if (driverClient[j].first != NA &&
            driverClient[j].second != NA)
        {
            int i1 = driverClient[j].first;
            int i2 = driverClient[j].second;
            if (isClientToAirport (i1) !=
                isClientToAirport (i2))
            { // CHK_TWO_SAME_TYPE
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "clients %d and %d "
                    "in the car are of "
                    "different types",
                    j, k + 1, i1, i2);
            }
            if (isClientToAirport (i1) &&
                isClientToAirport (i2) &&
                query[i1].to != query[i2].to)
            { // CHK_TWO_TO_AIRPORT_ID
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "clients %d and %d "
                    "in the car are going to "
                    "different airports "
                    "%d and %d",
                    j, k + 1, i1, i2,
                    query[i1].to,
                    query[i2].to);
            }
            if (isClientFromAirport (i1) &&
                isClientFromAirport (i2) &&
                query[i1].from != query[i2].from)
            { // CHK_TWO_FROM_AIRPORT_ID
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "clients %d and %d "
                    "in the car are taken from "
                    "different airports "
                    "%d and %d",
                    j, k + 1, i1, i2,
                    query[i1].from,
                    query[i2].from);
            }
            if (isClientFromAirport (i1) &&
                isClientFromAirport (i2) &&
                query[i1].moment != query[i2].moment)
            { // CHK_TWO_FROM_AIRPORT_MOMENT
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "clients %d and %d "
                    "in the car have arrived at "
                    "the airport at "
                    "different moments %d and %d",
                    j, k + 1, i1, i2,
                    query[i1].moment.value,
                    query[i2].moment.value);
            }
        }
    }

    void dropClient (int i, int j, int k, Time moment)
    {
        if (i < 0 || q <= i)
        { // CHK_QUERY_BOUNDS
            quitf (_wa, "driver %d "
                "after %d actions: "
                "invalid client %d",
                j, k, i);
        }
        if (clientState[i] != MOVING)
        {
            quitf (_wa, "driver %d "
                "after %d actions: "
                "dropping client %d "
                "who is not moving",
                j, k, i);
        }
        if (driverClient[j].first == i)
        {
            driverClient[j].first = NA;
        }
        else if (driverClient[j].second == i)
        {
            driverClient[j].second = NA;
        }
        else
        {
            quitf (_wa, "driver %d "
                "after %d actions: "
                "dropping client %d "
                "who is not in the car",
                j, k, i);
        }

        if (driverPos[j] != query[i].to)
        {
            quitf (_wa, "driver %d "
                "after %d actions: "
                "dropping client %d "
                "at %d instead of %d",
                j, k, i,
                driverPos[j],
                query[i].to);
        }

        Time finishMoment = moment + DROP_TIME;
        if (isClientFromAirport (i))
        {
            Time maxDuration = PICK_TIME +
                gtime[query[i].from][query[i].to] +
                DROP_TIME + MAX_EXTRA_TIME;
            Time actualDuration = finishMoment - query[i].moment;
            if (actualDuration > maxDuration)
            { // CHK_DURATION_FROM_AIRPORT
                quitf (_wa, "driver %d "
                    "after %d actions: "
                    "dropping client %d "
                    "until moment %d means "
                    "total query time %d, "
                    "but maximum allowed "
                    "time is %d", j, k, i,
                    finishMoment.value,
                    actualDuration.value,
                    maxDuration.value);
            }
        }
        if (isClientToAirport (i) &&
            finishMoment > query[i].moment)
        { // CHK_MOMENT_TO_AIRPORT
            quitf (_wa, "driver %d "
                "after %d actions: "
                "dropping client %d "
                "until moment %d, but "
                "must arrive no later "
                "than moment %d",
                j, k, i,
                finishMoment.value,
                query[i].moment.value);
        }
        clientState[i] = DROPPED;
    }

    SolutionResult expensesOfSolution (const Solution & solution)
    {
        clientState = vector <CLIENT_STATE> (q);
        clientCar = vector <int> (q);
        for (int i = 0; i < q; i++)
        {
            clientState[i] = WAITING;
            clientCar[i] = NA;
        }

        driverMoment = vector <Time> (d);
        driverTotalTime = vector <Time> (d);
        driverPreviousCommand = vector <COMMAND> (d);
        driverPos = vector <int> (d);
        driverClient = vector <pair <int, int> > (d);
        for (int j = 0; j < d; j++)
        {
            driverMoment[j] = driver[j].momentStart;
            driverTotalTime[j] = seconds (0);
            driverPreviousCommand[j] = NO_COMMAND;
            driverPos[j] = driver[j].garage;
            driverClient[j].first = NA;
            driverClient[j].second = NA;
        }

        if ((int) solution.instruction.size () != d)
        {
            quitf (_pe, "got %d drivers instead of %d",
                (int) solution.instruction.size (), d);
        }
        int64_t res = 0;
        int driversHired = 0;
        for (int j = 0; j < d; j++)
        {
            const vector <Instruction> & curList =
                solution.instruction[j];
            int curListLength = (int) curList.size ();
            if (curListLength > 0)
            {
                res += SALARY;
                driversHired++;
            }
            for (int k = 0; k < curListLength; k++)
            {
                const Instruction & cur = curList[k];
                Time moment = cur.moment;
                if (moment < driverMoment[j])
                { // CHK_TIME_FLOW
                    quitf (_wa, "driver %d "
                        "after %d actions: "
                        "free at moment %d, but next "
                        "action requested at moment %d",
                        j, k, driverMoment[j].value,
                        moment.value);
                }
                if (cur.command == MOVE)
                {
                    if (driverPreviousCommand[j] == MOVE)
                    { // CHK_NO_INTERMEDIATE
                        quitf (_wa, "driver %d "
                            "after %d actions: "
                            "next and previous "
                            "actions are move "
                            "commands", j, k);
                    }
                    int to = cur.arg1;
                    if (to < 0 || n <= to)
                    { // CHK_VERTEX_BOUNDS
                        quitf (_wa, "driver %d "
                            "after %d actions: "
                            "invalid destination %d",
                            j, k, to);
                    }
                    if (to == driverPos[j])
                    { // CHK_DIFF_VERTEX
                        quitf (_wa, "driver %d "
                            "after %d actions: "
                            "moving from %d to itself",
                            j, k, driverPos[j]);
                    }
                    Time duration =
                        gtime[driverPos[j]][to];
                    res += gdist[driverPos[j]][to];
                    driverTotalTime[j] += duration;
                    driverMoment[j] = moment + duration;
                    driverPos[j] = to;
                }
                else if (cur.command == PICK1 ||
                    cur.command == PICK2)
                {
                    pickClient (cur.arg1, j, k, moment);
                    if (cur.command == PICK2)
                    {
                        pickClient (cur.arg2,
                            j, k, moment);
                    }
                    driverMoment[j] = moment + PICK_TIME;
                }
                else if (cur.command == DROP1 ||
                    cur.command == DROP2)
                {
                    dropClient (cur.arg1, j, k, moment);
                    if (cur.command == DROP2)
                    {
                        dropClient (cur.arg2,
                            j, k, moment);
                    }
                    driverMoment[j] = moment + DROP_TIME;
                }
                else
                {
                    ensure (false);
                }
                driverPreviousCommand[j] = cur.command;
                if (driverMoment[j] > driver[j].momentFinish)
                {
                    quitf (_wa, "driver %d "
                        "after %d actions: "
                        "free at moment %d, but "
                        "should end work at moment %d",
                        j, k + 1,
                        driverMoment[j].value,
                        driver[j].momentFinish.value);
                }
                if (driverTotalTime[j] > MAX_DRIVING_TIME)
                { // CHK_DRIVER_SAFETY
                    quitf (_wa, "driver %d "
                        "after %d actions: "
                        "total driving time is %d, but "
                        "should be at most %d", j, k + 1,
                        driverTotalTime[j].value,
                        MAX_DRIVING_TIME.value);
                }
            }
        }

        for (int j = 0; j < d; j++)
        {
            if (driverPos[j] != driver[j].garage)
            {
                quitf (_wa, "driver %d ended "
                    "the day at %d instead of %d",
                    j, driverPos[j], driver[j].garage);
            }
        }

        int queriesMissed = 0;
        for (int i = 0; i < q; i++)
        {
            if (clientState[i] == WAITING)
            {
                res += PENALTY;
                queriesMissed++;
            }
            else if (clientState[i] != DROPPED)
            {
                quitf (_wa, "client %d ended "
                    "the day in car %d",
                    i, clientCar[i]);
            }
        }
        return SolutionResult (res, queriesMissed, q, driversHired, d);
    }
};

const Point Test::origin           = Point  (0, 0);
const int   Test::SALARY           =        300000; // CONST_SALARY
const int   Test::PENALTY          =       1500000; // CONST_PENALTY
const Time  Test::PICK_TIME        = seconds (600); // CONST_PICKUP
const Time  Test::DROP_TIME        = seconds (600); // CONST_DROPOFF
const Time  Test::MAX_DRIVING_TIME = hours     (9); // CONST_DRIVER_SAFETY
const Time  Test::MAX_EXTRA_TIME   = minutes  (60); // CONST_EXTRA_TIME

int main (int argc, char * argv [])
{
    setName ("checker for problem \"transfer\"");

    registerTestlibCmd (argc, argv);

    int64_t seed = inf.readLong ();

    Test test;
//  test.read (inf);
    test.generate ((unsigned) (seed));

    int64_t seedSolution = ouf.readLong ();
    ouf.readEoln ();
    if (seed != seedSolution)
    {
        quitf (_pe, "seed (first line) does not match input");
    }

    Solution solution;
    solution.read (ouf);

    double opt = test.expensesOptimistic ();
    SolutionResult res = test.expensesOfSolution (solution);
    double actual = res.expenses;

/*
    bool testingPolygon = true;
    // statistics to choose better constants
    double optDistance = test.distanceOptimistic ();
    double optDrivers = test.driversOptimistic ();
    double optDistancePercent = optDistance * 100.0 / opt;
    quitf (testingPolygon ? _ok : _pc (opt * 1000.0 / actual),
        "opt = %.0lf: %.0lf%% for average path %.0lf and "
        "%.0lf/%.0lf drivers; actual = %.0lf, ratio = %.3lf",
        opt, optDistancePercent, optDistance / test.q,
        optDrivers, test.d * 1.0, actual, opt / actual);
*/
    double score = opt * 1000.0 / actual;
    // shorter comment
    quitp (score, "%.0lf/%.0lf: miss %d/%d=q, hire %d/%d=d",
        opt, actual, res.queriesMissed, res.q, res.driversHired, res.d);
/*
    // longer comment
    quitp (score, "optimistic %.0lf, actual %.0lf: %d/%d queries missed, "
        "%d/%d drivers hired, score = %.3lf",
        opt, actual, res.queriesMissed, res.q,
        res.driversHired, res.d, score);
*/

    assert (false);
    return _fail;
}