Submission #1199679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199679		hyl_backup	The Kingdom of JOIOI (JOI17_joioi)	C++20	15 / 100	4099 ms	197940 KiB

joioi

//The Kingdom of JOIOI
#include <iostream>
#include <unordered_set>
#include <climits>
#include <vector>
#include <string>

#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )

long long h, w, min, max, col, a, b, min_a, min_b, max_a, max_b;
long long limit, ans;

long long mat[2007][2007];
int loga[2007] = {};
int expbin[12] = {};

//std::set<std::pair<long long, long long>> set;

void b_log(){
    long long bin=2;
    int cont = 1;
    expbin[0]=0;
    expbin[1]=1;
    for(int i = 1; i<2005; ++i){
        if(i>=bin){
            bin*=2;
            ++cont;
            expbin[cont]=i;
        }
        loga[i]=cont;
        //std::cout << loga[i] <<'\n';
    }
    bin = 1;
    for(int i = 0; i<11; ++i){

    }
}

struct sparse{
    std::vector<int> min;
    std::vector<int> max;
};

sparse table[2007][2007];

void b_sparse(){
    for(int i = h-1; i>=0; --i){
        table[col][i].min.push_back(mat[i][col]);
        table[col][i].max.push_back(mat[i][col]);
        for(int j = 1; j+i<h; j*=2){
            //std::cout << '-'<< i+j-j/2 <<' '<<j/2 <<':'<<loga[j/2]<< '_';
            table[col][i].min.push_back(MIN(table[col][i].min[loga[j/2]], table[col][i+j-j/2].min[loga[j/2]]));
            table[col][i].max.push_back(MAX(table[col][i].max[loga[j/2]], table[col][i+j-j/2].max[loga[j/2]]));
        }
        /*
        for(int x : table[col][i].min){
            std::cout << x <<' ';
        }
        std::cout << '\n';
        for(int x : table[col][i].max){
            std::cout << x <<' ';
        }
        std::cout << '\n';
       // */
    }
}

int min_tree(){
    int range=b-a;
    //std::cout <<b-expbin[loga[range]] <<" :2nd pos\n";
    return MIN(table[col][a].min[loga[range]], table[col][b-expbin[loga[range]]].min[loga[range]]);

}
int max_tree(){
    int range=b-a;
    return MAX(table[col][a].max[loga[range]], table[col][b-expbin[loga[range]]].max[loga[range]]);
}

struct hF
{
  size_t operator()(const std::vector<int> &vec) const
  {
    std::hash<int> hasher;
    size_t answer = 0;

    for (int i : vec)
    {
      answer ^= hasher(i) + 0x9e3779b9 +
                (answer << 6) + (answer >> 2);
    }
    return answer;
  }
};

std::unordered_set<std::vector<int>, hF> dp;
std::unordered_set<std::vector<int>, hF> dp2;

void increase(int j, std::unordered_set<std::vector<int>, hF> &sa, std::unordered_set<std::vector<int>, hF> &sb){
    for(std::vector<int> x : sa){
        //limit, min, max, min, max
        /*
        std::cout << j<<"pos ";
        for(int c : x){
            std::cout << c <<' ';
        }
        std::cout <<'\n';
        //*/

        limit=x[0];

        if(j==w){
            ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
            continue;
        }

        col= j;
        a=0;
        b=h-1;
        sb.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

        min=x[1];
        max=x[2];

        for(int i = 0; i<=limit; ++i){
            min = MIN(min, mat[i][j]);
            max = MAX(max, mat[i][j]);


            a=i+1;
            //std::cout << a << ':'<< b << ' ' << i << '\n';

            if(a<h){
                sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
            }
            else{
                sb.insert({i, min, max, x[3], x[4]});
            }
        }

    }
    sa.clear();
}

void decrease(int j, std::unordered_set<std::vector<int>, hF> &sa, std::unordered_set<std::vector<int>, hF> &sb){
    for(std::vector<int> x : sa){
        //limit, min, max, min, max
        /*
        std::cout << j<<"pos ";
        for(int c : x){
            std::cout << c <<' ';
        }
        std::cout <<'\n';
        //*/

        limit=x[0];

        if(j==w){
            ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
            continue;
        }

        col= j;
        a=0;
        b=h-1;
        //sb.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

        min=x[1];
        max=x[2];

        for(int i = 0; i<limit; ++i){
            min = MIN(min, mat[i][j]);
            max = MAX(max, mat[i][j]);
        }

        for(int i = limit; i<h; ++i){
            if(i>=0){
                min = MIN(min, mat[i][j]);
                max = MAX(max, mat[i][j]);
            }

            //std::cout <<min <<':' << max <<'\n';

            a=i+1;
            if(a<h){
                sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
            }
            else{
                sb.insert({i, min, max, x[3], x[4]});
            }
        }

    }
    sa.clear();
}
int main(){
    //std::cin.tie(0);
    //std::ios_base::sync_with_stdio(0);

    b_log();

    std::cin >> h >> w;

    for(int i = 0; i<h; ++i){
        for(int j = 0; j<w; ++j){
            std::cin >> mat[i][j];
            //og.insert(mat[i][j]);
        }
    }

    min = LLONG_MAX;

    for(int j = 0; j<w; ++j){
        col=j;
        b_sparse();
    }

    col = 0;

    a = 3;
    b = 4;
    //std::cout << min_tree() << ' ' << max_tree()<<'\n';

    //return 0;

    ans = LLONG_MAX;

    //ms_b=og;

    dp.insert({h-1, 2000123000, 0, 2000123000, 0});

    for(int j = 0; j<=w; ++j){
        if(j%2==0){
            increase(j, dp, dp2);
        }
        else{
            increase(j, dp2, dp);
        }
    }

    //return 0 ;
    //std::cout << "prelim: " << ans <<'\n';

    dp.clear();
    dp2.clear();

    dp.insert({-1, 2000123000, 0, 2000123000, 0});

    for(int j = 0; j<=w; ++j){
        if(j%2==0){
            decrease(j, dp, dp2);
        }
        else{
            decrease(j, dp2, dp);
        }
    }

    std::cout << ans;

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'void increase(int, std::unordered_set<std::vector<int>, hF>&, std::unordered_set<std::vector<int>, hF>&)':
joioi.cpp:134:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  134 |                 sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                               ^~~
joioi.cpp:134:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:134:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  134 |                 sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                    ^~~
joioi.cpp:134:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:137:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  137 |                 sb.insert({i, min, max, x[3], x[4]});
      |                               ^~~
joioi.cpp:137:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:137:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  137 |                 sb.insert({i, min, max, x[3], x[4]});
      |                                    ^~~
joioi.cpp:137:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp: In function 'void decrease(int, std::unordered_set<std::vector<int>, hF>&, std::unordered_set<std::vector<int>, hF>&)':
joioi.cpp:186:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  186 |                 sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                               ^~~
joioi.cpp:186:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:186:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  186 |                 sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                    ^~~
joioi.cpp:186:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:189:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  189 |                 sb.insert({i, min, max, x[3], x[4]});
      |                               ^~~
joioi.cpp:189:31: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:189:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  189 |                 sb.insert({i, min, max, x[3], x[4]});
      |                                    ^~~
joioi.cpp:189:36: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp: In function 'int main()':
joioi.cpp:230:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]
  230 |     dp.insert({h-1, 2000123000, 0, 2000123000, 0});
      |                ~^~
joioi.cpp:230:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]

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