oj.uz

답안 #292247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292247 2020-09-06T15:25:15 Z Nucleist 삶의 질 (IOI10_quality) C++14
60 / 100
 5000 ms 21240 KB 
#include "quality.h"
//Self-control leads to consistency.
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std; 
using namespace __gnu_pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll int
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
typedef tree<
 int,
 null_type,
 less<int>,
 rb_tree_tag,
 tree_order_statistics_node_update> ord;
ord X;
int q[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			int hs=W*i+j;
			X.insert(Q[i][j]);
		}
	}
	int dir=0;
	int curx=0,cury=0;
	ll ans=INF;
	while(1){
		if(!dir){
			if(cury+W-1<C){
				int last=cury-1;
				if(last>=0){
					for (int i = 0; i < H; ++i)
					{
						int z=curx+i,za=last;
						X.erase(Q[z][za]);
					}
				}
				for (int i = 0; i < H; ++i)
				{
					int z=curx+i,za=cury+W-1;
					X.insert(Q[z][za]);
				}
				auto u=*X.find_by_order(sz(X)/2);
				//debug(u.first)
				ans=min(ans,(u));
				cury++;
			}
			else if(curx+H<R){
				//debug(1)
				cury--;
				curx++;
				if(curx-1>=0){
					for (int i = 0; i < W; ++i)
					{
						int xa=curx-1,ya=i+cury;
						//debugs(xa,ya)
						X.erase(Q[xa][ya]);
					}
				}
				for (int i = 0; i < W; ++i)
				{
					int xa=curx+H-1,ya=i+cury;
					X.insert(Q[xa][ya]);
				}
				auto u=*X.find_by_order(sz(X)/2);
				//debug(u.first)
				ans=min(ans,(u));
				dir=1-dir;
			}
			else {
				return ans;
			}
		}
		else{
			if(cury>=0){
				int last=cury+W;
				if(last<C){
					for (int i = 0; i < H; ++i)
					{
						int z=curx+i,za=last;
						X.erase(Q[z][za]);
					}
				}
				for (int i = 0; i < H; ++i)
				{
					int z=curx+i,za=cury;
					X.insert(Q[z][za]);
				}
				auto u=*X.find_by_order(sz(X)/2);
				//debug(u.first)
				ans=min(ans,(u));
				cury--;
			}
			else if(curx+H<R){
				cury++;
				curx++;
				if(curx-1>=0){
					for (int i = 0; i < W; ++i)
					{
						int xa=curx-1,ya=i+cury;
						X.erase(Q[xa][ya]);
					}
				}
				for (int i = 0; i < W; ++i)
				{
					int xa=curx+H-1,ya=i+cury;
					X.insert(Q[xa][ya]);
				}
				auto u=*X.find_by_order(sz(X)/2);
				//debug(u.first)
				ans=min(ans,(u));
				dir=1-dir;
			}
			else {return ans;}
		}
	}
	return ans;
}

Compilation message

quality.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("O3")
      | 
quality.cpp:10: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("unroll-loops")
      | 
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:48:8: warning: unused variable 'hs' [-Wunused-variable]
   48 |    int hs=W*i+j;
      |        ^~
quality.cpp: In function 'void setIO(std::string)':
quality.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
quality.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 1024 KB Output is correct
5 Correct 61 ms 896 KB Output is correct
6 Correct 17 ms 1152 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 1024 KB Output is correct
5 Correct 61 ms 896 KB Output is correct
6 Correct 17 ms 1152 KB Output is correct
7 Correct 2071 ms 3728 KB Output is correct
8 Correct 110 ms 4344 KB Output is correct
9 Correct 1855 ms 3124 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 1024 KB Output is correct
5 Correct 61 ms 896 KB Output is correct
6 Correct 17 ms 1152 KB Output is correct
7 Correct 2071 ms 3728 KB Output is correct
8 Correct 110 ms 4344 KB Output is correct
9 Correct 1855 ms 3124 KB Output is correct
10 Execution timed out 5015 ms 21240 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 1024 KB Output is correct
5 Correct 61 ms 896 KB Output is correct
6 Correct 17 ms 1152 KB Output is correct
7 Correct 2071 ms 3728 KB Output is correct
8 Correct 110 ms 4344 KB Output is correct
9 Correct 1855 ms 3124 KB Output is correct
10 Execution timed out 5015 ms 21240 KB Time limit exceeded
11 Halted 0 ms 0 KB -