Submission #50264

#	Time	Username	Problem	Language	Result	Execution time	Memory
50264		gs13105	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1090 ms	265212 KiB

joioi

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

int mn, mx, h, w;
int arr[2010][2010];

bool solve(int lt, int gt)
{
    int p = w, i, j;
    for(i = 0; i < h; i++)
    {
        for(j = 0; j < w && j < p; j++)
            if(arr[i][j] > lt)
                break;
        p = j;
        for(j = p; j < w; j++)
            if(arr[i][j] < gt)
                return 0;
    }
    return 1;
}

void horflip()
{
    for(int i = 0; i < h; i++)
        reverse(arr[i], arr[i] + w);
}

void valflip()
{
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            arr[i][j] = mx - arr[i][j];
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int i, j;
    scanf("%d%d", &h, &w);
    for(i = 0; i < h; i++)
        for(j = 0; j < w; j++)
            scanf("%d", &arr[i][j]);

    mn = mx = arr[0][0];
    for(i = 0; i < h; i++)
    {
        for(j = 0; j < w; j++)
        {
            mn = min(mn, arr[i][j]);
            mx = max(mx, arr[i][j]);
        }
    }

    mx -= mn;
    for(i = 0; i < h; i++)
        for(j = 0; j < w; j++)
            arr[i][j] -= mn;

    int s, g;
    s = 0;
    g = mx;
    while(s < g)
    {
        int x = (s + g) / 2;

        if(solve(x, mx - x))
        {
            g = x;
            continue;
        }

        valflip();

        if(solve(x, mx - x))
        {
            g = x;
            continue;
        }

        horflip();

        if(solve(x, mx - x))
        {
            g = x;
            continue;
        }

        valflip();

        if(solve(x, mx - x))
        {
            g = x;
            continue;
        }

        s = x + 1;
    }
    printf("%d\n", s);
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &h, &w);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40