oj.uz

Submission #240650

# Submission time Handle Problem Language Result Execution time Memory
240650 2020-06-20T12:05:00 Z robertnovistan Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 219 ms 12884 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;

const int INFINI = (2000 * 1000 * 1000);
const int MAX_STEAKS = (200 * 1000);

int Steaks[MAX_STEAKS][4];

int PossiblesPiques[4][2];

int Choisi[4];

pair <int, int> Horizontaux[MAX_STEAKS];
pair <int, int> Verticaux[MAX_STEAKS];

int nbSteaks, nbPiques;

void Read() {
    scanf("%lld%lld", &nbSteaks, &nbPiques);
    for (int i = 0; i < nbSteaks; i ++)
    {
        for (int j = 0; j < 4; j ++)
        {
            scanf("%lld", &Steaks[i][j]);
        }
        Horizontaux[i] = make_pair(Steaks[i][0], ++ Steaks[i][2]);
        Verticaux[i] = make_pair(Steaks[i][1], ++ Steaks[i][3]);
    }
    sort(Horizontaux, Horizontaux + nbSteaks);
    sort(Verticaux, Verticaux + nbSteaks);
    return;
}

void TraiteHorizontaux() {
    int nbPik = 0;
    int act = 0;
    int minfin = INFINI;
    while (act < nbSteaks)
    {
        if (Horizontaux[act].first >= minfin)
        {
            PossiblesPiques[nbPik ++][0] = minfin - 1;
            minfin = INFINI;
        }
        minfin = min(minfin, Horizontaux[act].second);
        act ++;
    }
    PossiblesPiques[nbPik ++][0] = minfin - 1;
    for (int i = nbPik; i < nbPiques; i ++)
    {
        PossiblesPiques[i][0] = PossiblesPiques[i - 1][0];
    }
    return;
}

void TraiteVerticaux() {
    int nbPik = 0;
    int act = 0;
    int minfin = INFINI;
    while (act < nbSteaks)
    {
        if (Verticaux[act].first >= minfin)
        {
            PossiblesPiques[nbPik ++][1] = minfin - 1;
            minfin = INFINI;
        }
        minfin = min(minfin, Verticaux[act].second);
        act ++;
    }
    PossiblesPiques[nbPik ++][1] = minfin - 1;
    for (int i = nbPik; i < nbPiques; i ++)
    {
        PossiblesPiques[i][1] = PossiblesPiques[i - 1][1];
    }
    return;
}

bool Inter(int i, int lig, int col) {
    return Steaks[i][0] <= lig && lig < Steaks[i][2] && Steaks[i][1] <= col && col < Steaks[i][3];
}

bool Verify() {
    for (int i = 0; i < nbSteaks; i ++)
    {
        bool t = false;
        for (int j = 0; j < nbPiques; j ++)
        {
            if (Inter(i, PossiblesPiques[j][0], Choisi[j]))
            {
                t = true;
            }
        }
        if (!t)
        {
            return false;
        }
    }
    return true;
}

bool Choose(int cur) {
    if (cur == nbPiques)
    {
        return Verify();
    }
    for (int i = 0; i < nbPiques; i ++)
    {
        Choisi[cur] = PossiblesPiques[i][1];
        if (Choose(cur + 1))
        {
            return true;
        }
    }
    return false;
}

void Solve() {
    if (Choose(0))
    {
        //printf("42\n");
    }
    for (int i = 0; i < nbPiques; i ++)
    {
        printf("%lld %lld\n", PossiblesPiques[i][0], Choisi[i]);
    }
    return;
}

void Print() {
    for (int i = 0; i < nbSteaks; i ++)
    {
        //printf("%d %d\n", Horizontaux[i].first, Horizontaux[i].second);
    }
    for (int i = 0; i < nbSteaks; i ++)
    {
        //printf("%d %d\n", Verticaux[i].first, Verticaux[i].second);
    }
    for (int i = 0; i < nbPiques; i ++)
    {
        //printf("%d %d\n", PossiblesPiques[i][0], PossiblesPiques[i][1]);
    }
    return;
}

signed main() {
    Read();
    TraiteHorizontaux();
    TraiteVerticaux();
    Solve();
    Print();
    return 0;
}

Compilation message

hamburg.cpp: In function 'void Read()':
hamburg.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%lld%lld", &nbSteaks, &nbPiques);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |             scanf("%lld", &Steaks[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Incorrect 3 ms 512 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Incorrect 3 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 216 ms 12792 KB Output is correct
6 Correct 219 ms 12792 KB Output is correct
7 Correct 204 ms 12792 KB Output is correct
8 Correct 208 ms 12884 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Incorrect 3 ms 512 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Incorrect 3 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -