oj.uz

Submission #738507

# Submission time Handle Problem Language Result Execution time Memory
738507 2023-05-09T01:01:51 Z grossly_overconfident Quality Of Living (IOI10_quality) C++17
60 / 100
 5000 ms 26704 KB 
#include <bits/stdc++.h>
using namespace std;

void chuck(set<int>::iterator& mid, set<int>& s, int in, set<int>::iterator& out){
	if (*mid == *out){
		if (in > *mid){
			s.insert(in);
			++mid;
			s.erase(out);
			return;
		}
		s.insert(in);
		--mid;
		s.erase(out);
		return;
	}
    if (in < *mid && *mid < *out){
        s.insert(in);
		--mid;
		s.erase(out);
		return;
    }
    if (*out < *mid && *mid < in){
        s.insert(in);
		++mid;
		s.erase(out);
		return;
    }
    s.insert(in);
    s.erase(out);
    return;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	set<int> s;
	for (int i = 0; i < H; ++i){
		for (int j = 0; j < W; ++j){
			s.insert(Q[i][j]);
		}
	}
	auto mid = s.begin();
	for (int i = 0; i < (s.size() - 1) / 2; ++i){
		mid++;
	}
	int best = *mid;
	for (int i = 0; i < C - W + 1; ++i){
		for (int j = 0; j < R - H + 1; ++j){
            if (i == C - W && j == R - H){
                break;
            }
            if (i % 2 == 0){
                if (j == R - H){
                    for (int k = 0; k < H; ++k){
                        auto out = s.find(Q[j + k][i]);
                        chuck(mid, s, Q[j + k][i + W], out);
                    }
                }
                else{
                    for (int k = 0; k < W; ++k){
                        auto out = s.find(Q[j][i + k]);
                        chuck(mid, s, Q[j + H][i + k], out);
                    }
                }
            }
            else{
                int p = R - H - j;
                if (p == 0){
                    for (int k = 0; k < H; ++k){
                        auto out = s.find(Q[p + k][i]);
                        chuck(mid, s, Q[p + k][i + W], out);
                    }
                }
                else{
                    for (int k = 0; k < W; ++k){
                        auto out = s.find(Q[p + H - 1][i + k]);
                        chuck(mid, s, Q[p - 1][i + k], out);
                    }
                }
            }
            best = min(best, *mid);
		}
	}
    return best;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < (s.size() - 1) / 2; ++i){
      |                  ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 30 ms 936 KB Output is correct
5 Correct 28 ms 808 KB Output is correct
6 Correct 12 ms 1080 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 30 ms 936 KB Output is correct
5 Correct 28 ms 808 KB Output is correct
6 Correct 12 ms 1080 KB Output is correct
7 Correct 1052 ms 3652 KB Output is correct
8 Correct 104 ms 4312 KB Output is correct
9 Correct 1099 ms 3048 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 30 ms 936 KB Output is correct
5 Correct 28 ms 808 KB Output is correct
6 Correct 12 ms 1080 KB Output is correct
7 Correct 1052 ms 3652 KB Output is correct
8 Correct 104 ms 4312 KB Output is correct
9 Correct 1099 ms 3048 KB Output is correct
10 Execution timed out 5030 ms 26704 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 30 ms 936 KB Output is correct
5 Correct 28 ms 808 KB Output is correct
6 Correct 12 ms 1080 KB Output is correct
7 Correct 1052 ms 3652 KB Output is correct
8 Correct 104 ms 4312 KB Output is correct
9 Correct 1099 ms 3048 KB Output is correct
10 Execution timed out 5030 ms 26704 KB Time limit exceeded
11 Halted 0 ms 0 KB -