Submission #579958

#	Time	Username	Problem	Language	Result	Execution time	Memory
579958		web	Chess Rush (CEOI20_chessrush)	C++17	0 / 100	1 ms	212 KiB

chessrush

#include <unordered_set>
#include "arithmetics.h"
#include <iostream>
#include <vector>
#include <climits>
#include <set>
using namespace std;

pair<long long, long long> calcWaysRook(pair<long long, long long> start, pair<long long, long long> end)
{
    if(start.second == end.second)
    {
        return {1,1};
    }
    else
    {
        return {2,2};
    }
}

bool reachableForQueenInOneMove(pair<long long, long long> start, pair<long long, long long> end, long long numRows, long long numCols)
{
    if(start.first > numRows || start.second > numCols || start.first <= 0 ||start.second <= 0)
        return false;
    return start.second == end.second ||( abs(start.second - end.second) == end.first-start.first);
}

class Punkt
{public:
    long long x; long long y;
    Punkt()
    {

    };
    Punkt(int xn, int yn)
    :x(xn), y(yn)
    {

    };
    bool operator!=(const Punkt& other)
    {
        return !(other.x == x && other.y == y);
    }
    bool operator==(const Punkt& other)
    {
        return other.x == x && other.y == y;
    }
    bool operator<(const Punkt& other)
    {
        if(x<other.x)
            return true;
        else
            return y < other.y;
    }
};
class Gerade
{
    public:
    long long m, b;
    Punkt p1, p2;
    Gerade(Punkt pt1, Punkt pt2)
    :
    p1(pt1),
    p2(pt2)
    {
        if(( pt2.x - pt1.x) ==0)
        {
            m = INT_MAX;
            b = pt2.x;
        }
        else
        {
        m = (pt2.y -pt1.y) /( pt2.x - pt1.x);
         b = pt2.y - m*pt2.x;
        }
       
    }
    long long f(long long x)
    {
        return m*x +b;
    }

    Punkt intersection(const Gerade& other)
    {
        long long zaehler = other.b - b;
        long long nenner = m - other.m;
        if(m == INT_MAX)
        {
            if(other.m == INT_MAX)
                return Punkt(-1,-1);
            else
                return Punkt(b, other.m+b + other.b);
        }
        if(other.m == INT_MAX)
        {
            return Punkt(other.b, m*other.b + b);
        }
        if(nenner == 0)
            return Punkt(-1,-1);
        if(zaehler % nenner == 0)
        {
            return Punkt(zaehler / nenner, f(zaehler/nenner));
        }
        else
        {
            return {-1,-1};
        }
    }
};
vector<Gerade> generateLinesQueen(Punkt start)
{
    vector<Gerade> v;
     v.push_back(Gerade(start, Punkt(start.x+1, start.y-1)));
    v.push_back(Gerade(start, Punkt(start.x-1, start.y)));
    v.push_back(Gerade(start, Punkt(start.x-1, start.y-1)));
    v.push_back(Gerade(start, Punkt(start.x+1, start.y)));
    v.push_back(Gerade(start, Punkt(start.x, start.y-1)));
    return v;
}



vector<Punkt> getIntersections(vector<Gerade> v1, vector<Gerade> v2)
{
    vector<pair<long long, long long>> v;
    for(auto g : v1)
    {
        for(auto f:v2)
        {
            Punkt inter = g.intersection(f);
            if(inter != Punkt(-1,-1))
                v.push_back({inter.x, inter.y});
        }
    }
    set<pair<long long, long long>> s(v.begin(), v.end());
    vector<Punkt> vf;
    for(auto it : s)
        vf.push_back(Punkt(it.first, it.second));
    return vf;
}

long long numQueenWays(Punkt start, Punkt end, long long numR, long long numC)
{
    start = Punkt(start.y, start.x);
    end = Punkt(end.y, end.x);
    long long res = 0;
    vector<Gerade> gStart = generateLinesQueen(start);
    vector<Gerade> gEnd = generateLinesQueen(end);
    vector<Punkt> intersections = getIntersections(gStart, gEnd);
    for(auto p : intersections)
    {
        if(p.x > 0 && p.x <= numC && p.y > 0 && p.y <= numR)
            res++;
        
    }
    for(auto p : intersections)
    {
        if(p == start || p == end)
            return -2;
    }
    return res;
}

/*
pair<long long, long long> calcWaysQueen(long long numR, long long numC, pair<long long, long long> start, pair<long long, long long> end)
{
    if(start.second == end.second || (abs(start.second - end.second) == end.first-start.first))
    {
        return {1,1};
    }
    else
    {
        int numPaths = 4;
        //try all directions
       

        //straight to other side then diagonal /diagonal the nstraight
        if(start.second < end.second)
        {
            long long wantStartCol = end.second - (end.first - start.first);
            if(reachableForQueenInOneMove({start.first, wantStartCol}, end, numR, numC))
                numPaths++;
            if(reachableForQueenInOneMove(start, {end.first, end.second + abs(start.second - wantStartCol)}, numR, numC))
                numPaths++;
        }
        //diagonal the ndiagonal

    }
}
*/
int main()
{
    long long R, Q,C;
    cin>>R>>C>>Q;
    while(Q--)
    {
        char type; cin>>type;
        long long col1, col2;
        cin>>col1>>col2;
        switch(type)
        {
            case 'P':
                {
                    std::cout<<0<<" "<<0<<endl;
                    break;
                }
            case 'Q':{
                long long qW = numQueenWays(Punkt(col1, 1), Punkt(col2, R), R, C);
                if(qW == -2)
                    std::cout<<1<<" "<<1<<endl;
                else
                    std::cout<<2<<" "<<qW<<endl;
                break;}
            case 'R':{
                pair<long long, long long> rookW = calcWaysRook({1, col1}, {R, col2});
                std::cout<<rookW.first<<" "<<rookW.second<<endl;
                break;}
            default:
            {
                break;
            }
           
        }
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 0 / 5
• Subtask 6: 0 / 8
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7