Submission #882971

#	Time	Username	Problem	Language	Result	Execution time	Memory
882971		Tudy006	Robots (IOI13_robots)	C++14	0 / 100	1 ms	4544 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

int maxVec( int n, int* v ) {
    int x = 0;
    for ( int i = 0; i < n; i ++ ) {
        x = max( x, v[i] );
    }
    return x;
}

unordered_map <int, int> cod;

void normalize( vector <int> values ) {
    cod.clear();
    sort( values.begin(), values.end() );
    cod[values[0]] = 1;
    for ( int i = 1; i < values.size(); i ++ ) {
        if ( values[i] != values[i - 1] ) cod[values[i]] = cod[values[i - 1]] + 1;
    }
}

void normVec( int n1, int n2, int v1[], int v2[] ) {
    vector <int> values;
    for ( int i = 0; i < n1; i ++ ) values.push_back( v1[i] );
    for ( int i = 0; i < n2; i ++ ) values.push_back( v2[i] );
    normalize( values );
    for ( int i = 0; i < n1; i ++ ) v1[i] = cod[v1[i]];
    for ( int i = 0; i < n2; i ++ ) v2[i] = cod[v2[i]];
}

int sumRect( const vector<vector<int>>& a, int l1, int c1, int l2, int c2 ) {
    return a[l2][c2] - a[l2][c1 - 1] - a[l1 - 1][c2] + a[l1 - 1][c1 - 1];
}
int tavan( int a, int b ) {
    if ( b == 0 ) {
        if ( a == 0 ) return 0;
        return 1e9;
    }
    return ( a - 1 ) / b + 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[] ) {
    normVec( A, T, X, W );
    normVec( B, T, Y, S );
    int maxX = maxVec( A, X ), maxY = maxVec( B, Y );

    for ( int i = 0; i < T; i ++ ) {
        if ( W[i] > maxX && S[i] > maxY ) return -1;
    }

    vector <vector<int>> sum( maxX + 2 );
    for ( int i = 0; i <= maxX + 1; i ++ ) sum[i].resize( maxY + 2 );
    for ( int i = 0; i < T; i ++ ) sum[min( W[i], maxX + 1 )][min( S[i], maxY + 1 )] = 1;

    for ( int i = 1; i <= maxX + 1; i ++ ) {
        sum[i][0] += sum[i - 1][0];
    }
    for ( int i = 1; i <= maxY + 1; i ++ ) {
        sum[0][i] += sum[0][i - 1];
    }
    for ( int i = 1; i <= maxX + 1; i ++ ) {
        for ( int j = 1; j <= maxY + 1; j ++ ) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int ans = ( T - 1 ) / ( A + B ) + 1;
    for ( int i = 0; i < A; i ++ ) {
        ans = max( ans, tavan( sumRect( sum, X[i], 1, maxX + 1, maxY + 1 ), A - i - 1 + B ) );
        for ( int j = 0; j < B; j ++ ) {
            int rap = tavan( sumRect( sum, X[i], Y[j], maxX + 1, maxY + 1 ), A - i + B - j - 2 );
            ans = max( ans, rap );
        }
    }
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'void normalize(std::vector<int>)':
robots.cpp:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for ( int i = 1; i < values.size(); i ++ ) {
      |                      ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10