Submission #292247

#	Time	Username	Problem	Language	Result	Execution time	Memory
292247		Nucleist	Quality Of Living (IOI10_quality)	C++14	60 / 100	5015 ms	21240 KiB

quality

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20