oj.uz

Submission #91923

# Submission time Handle Problem Language Result Execution time Memory
91923 2018-12-31T13:55:07 Z Retro3014 Treasure (different grader from official contest) (CEOI13_treasure2) C++17
100 / 100
 2 ms 764 KB 
#include "treasure.h"
#define MAX_N 100
#include <vector>
#include <stdio.h>

using namespace std;


int sumx[MAX_N+1], sumy[MAX_N+1];
int arr[MAX_N+1][MAX_N+1];
int dp[4][MAX_N+1][MAX_N+1];
int vst[4][MAX_N+1][MAX_N+1];
int all;
int c(int x, int y, int z, int w){
    return countTreasure(x, y, z, w);
}
int n;

vector<pair<int, int>> ans;

int calc(int x, int y, int z, int w){
    if(z==n && w==n){
        if(!vst[0][x][y]){
            dp[0][x][y]=c(x, y, z, w); vst[0][x][y]=true;
        }return dp[0][x][y];
    }
    if(x==1 && y==1){
        if(!vst[1][z][w]){
            dp[1][z][w]=c(x, y, z, w); vst[1][z][w]=true;
        }return dp[1][z][w];
    }
    if(x==1 && w==n){
        if(!vst[2][z][y]){
            dp[2][z][y]=c(x, y, z, w); vst[2][z][y]=true;
        }return dp[2][z][y];
    }
    if(y==1 && z==n){
        if(!vst[3][x][w]){
            dp[3][x][w]=c(x, y, z, w); vst[3][x][w]=true;
        }return dp[3][x][w];
    }
    return 0;
}

void set(int x, int y, int z, int w, int t){
    if(z==n && w==n){
        vst[0][x][y]=true;
        dp[0][x][y]=t; return;
    }
    if(x==1 && y==1){
        vst[1][z][w]=true;
        dp[1][z][w]=t;
        return;
    }
    if(x==1 && w==n){
        vst[2][z][y]=true;
        dp[2][z][y]=t;
        return;
    }
    if(y==1 && z==n){
        vst[3][x][w]=true;
        dp[3][x][w]=t;
        return;
    }
    return;
}

int kx, ky, k;

void findTreasure (int N) {n=N;
    all=calc(1, 1, N, N);
    int T = (N+1)/2;
    kx=0; ky=0;
    for(int i=1; i<T; i++){
        sumx[i]=calc(i+1, 1, N, N); sumy[i]=calc(1, i+1, N, N);
        sumx[i]=all-sumx[i]-kx; sumy[i]=all-sumy[i]-ky;
        kx+=sumx[i]; ky+=sumy[i];
    }
    sumx[T]=all-kx;  sumy[T]=all-ky;
    kx=0; ky=0;
    for(int i=N; i>T; i--){
        sumx[i]=calc(1, 1, i-1, N); sumy[i]=calc(1, 1, N, i-1);
        sumx[i]=all-sumx[i]-kx; sumy[i]=all-sumy[i]-ky;
        kx+=sumx[i]; ky+=sumy[i];
    }
    sumx[T]-=kx; sumy[T]-=ky;
    k=0;    for(int i=1; i<=T; i++){k+=sumy[i];} set(1, 1, N, T, k);
    k=0;    for(int i=T; i<=N; i++){k+=sumy[i];} set(1, T, N, N, k);
    k=0;    for(int i=1; i<=T; i++){k+=sumx[i];} set(1, 1, T, N, k);
    k=0;    for(int i=T; i<=N; i++){k+=sumx[i];} set(T, 1, N, N, k);
    
    
    
    
    for(int i=1; i<T; i++){
        for(int j=1; j<T; j++){
            arr[i][j]=calc(i, j, N, N)-calc(i+1, j, N, N)-calc(i, j+1, N, N)+calc(i+1, j+1, N, N);
            if(arr[i][j]==1)    ans.push_back(make_pair(i, j));
        }
    }
    for(int i=1; i<T; i++){
        for(int j=T+1; j<=N; j++){
            arr[i][j]=calc(i, 1, N, j)-calc(i+1, 1, N, j)-calc(i, 1, N, j-1)+calc(i+1, 1, N, j-1);
            if(arr[i][j]==1)    ans.push_back(make_pair(i, j));
        }
    }
    for(int i=T+1; i<=N; i++){
        for(int j=1; j<T; j++){
            arr[i][j]=calc(1, j, i, N)-calc(1, j, i-1, N)-calc(1, j+1, i, N)+calc(1, j+1, i-1, N);
            if(arr[i][j]==1)    ans.push_back(make_pair(i, j));
        }
    }
    for(int i=T+1; i<=N; i++){
        for(int j=T+1; j<=N; j++){
            arr[i][j]=calc(1, 1, i, j)-calc(1, 1, i-1, j)-calc(1, 1, i, j-1)+calc(1, 1, i-1, j-1);
            if(arr[i][j]==1)    ans.push_back(make_pair(i, j));
        }
    }
    for(int i=1; i<=N; i++){
        if(i!=T){
            k=sumx[i];
            for(int j=1; j<=N; j++){
                if(j!=T){
                    k-=arr[i][j];
                }
            }
            arr[i][T]=k;
            if(arr[i][T]==1)    ans.push_back(make_pair(i, T));
            k=sumy[i];
            for(int j=1; j<=N; j++){
                if(j!=T){
                    k-=arr[j][i];
                }
            }
            arr[T][i]=k;
            if(arr[T][i]==1)    ans.push_back(make_pair(T, i));
        }
    }
    k=all;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!(i==T && j==T)){
                k-=arr[i][j];
            }
        }
    }
    arr[T][T]=k;
    if(arr[T][T]==1)    ans.push_back(make_pair(T, T));
    for(int i=0; i<ans.size(); i++){
        Report(ans[i].first, ans[i].second);
    }
    /*for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }//*/
}

Compilation message

treasure.cpp: In function 'void findTreasure(int)':
treasure.cpp:149:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++){
                  ~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct - N = 5, K = 289, score = 10
2 Correct 2 ms 376 KB Output is correct - N = 10, K = 4475, score = 10
3 Correct 2 ms 376 KB Output is correct - N = 15, K = 22289, score = 10
4 Correct 2 ms 376 KB Output is correct - N = 16, K = 28928, score = 10
5 Correct 2 ms 508 KB Output is correct - N = 55, K = 4005289, score = 10
6 Correct 2 ms 504 KB Output is correct - N = 66, K = 8305803, score = 10
7 Correct 2 ms 632 KB Output is correct - N = 77, K = 15383161, score = 10
8 Correct 2 ms 632 KB Output is correct - N = 88, K = 26244416, score = 10
9 Correct 2 ms 732 KB Output is correct - N = 99, K = 42032201, score = 10
10 Correct 2 ms 764 KB Output is correct - N = 100, K = 43760000, score = 10