Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Posted by longsunsp at 2017-11-02 17:33:00 on Problem 1009
```#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int size = 1000;
const int out_size = 8000;
int pairs[size][2];
int output[out_size][2];
int mmax(int a, int b){
return a > b ? a : b;
}
int abss(int a, int b){
if (a > b) return a - b;
else return b - a;
}
int width = 0;
int pixel_num = 0;
int len = 0;
int out_len = 0;
int height = 0;
int cache[out_size];
int get_value(int pos){
int i = 0, j = 0;
while (j < pos){
j += pairs[i++][1];
}
return pairs[i-1][0];
}
int get_max(int pos){
int row = (pos-1) / width;
int col = (pos-1) % width;
int p = get_value(pos);
int max12 = 0;
for (int i = row - 1; i < row + 2;i++){
for (int j = col - 1; j < col + 2;j++){
int tmp_pos = i*width + j;
if (i < 0 || j < 0 || j >= width || (i == row && j == col) || tmp_pos >= pixel_num) continue;
int v = get_value(tmp_pos+1);
//cout << "p: " << p << " v: " << v << endl;
max12 = mmax(max12, abss(p, v));
}
}
//cout <<"row:"<<row<<" col:"<<col<< " max : " << max12 << endl;
return max12;
}
void exchange(int arr[out_size][2], int i, int j){
int t[2];
t[0] = arr[j][0];
t[1] = arr[j][1];
arr[j][0] = arr[i][0];
arr[j][1] = arr[i][1];
arr[i][0] = t[0];
arr[i][1] = t[1];
}
int partition(int arr[out_size][2], int p, int r){
int i = p - 1;
int pivot = arr[r][0];
for (int j = p; j < r; j++){
if (arr[j][0] < pivot){
i++;
exchange(arr, i, j);
}
}
exchange(arr, i+1, r);
return i + 1;
}
void quicksort(int arr[out_size][2], int p, int r){
if (p < r){
int q = partition(arr, p, r);
quicksort(arr, p, q - 1);
quicksort(arr, q + 1, r);
}
}
int main(){
//freopen("Text.txt", "r", stdin);
int value, num;
width = 0;
while (cin >> width && width != 0){
len = 0;
pixel_num = 0;
out_len = 0;
while (cin >> value >> num && num > 0){
pairs[len][0] = value;
pairs[len++][1] = num;
pixel_num += num;
}

height = pixel_num / width;
int pos = 1;
int index = 0;
for (int p = 0; p < len; p++){
int row = (pos -1) / width;
int col = (pos -1) % width;
for (int i = row - 1; i < row + 2; i++){
for (int j = col - 1; j < col + 2; j++){
int tmp_pos = i*width + j;
if (i < 0 || j < 0 || tmp_pos >= pixel_num) continue;
output[index][0] = tmp_pos+1;
int v = get_max(tmp_pos+1);
output[index++][1] = v;
}
}
pos += pairs[p][1];
}

///head point at the last line
int tmp_pos = (height-1)*width;
output[index][0] = tmp_pos+1;
output[index++][1] = get_max(tmp_pos+1);

///last point at the last line
tmp_pos = pixel_num - 1;
output[index][0] = tmp_pos;
output[index++][1] = get_max(tmp_pos);
quicksort(output, 0, index-1);
/*
cout << "================================================" << endl;
for (int i = 0; i < index; i++){
cout << output[i][0] << "  " << output[i][1] << endl;
}
cout << "================================================" << endl;
*/
cout << width << endl;
int res_value = output[0][1];
int start_pos = 1;
for (int i = 0; i < index; i++){
if (output[i][1] == res_value) continue;
cout << res_value << " " << output[i][0] - start_pos<< endl;
start_pos = output[i][0];
res_value = output[i][1];
}
cout << res_value << " " << pixel_num - start_pos +1<< endl;
cout << "0 0" << endl;
}
cout << "0" << endl;
return 0;
}```

Followed by: