Submission #71527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71527	2018-08-25T03:56:12 Z	zigui(#2223)	행성 탐사 (GA8_planet)	C++11	Compilation error	0 ms	0 KB

planet

#include<assert.h>
#include<tuple>
#include<set>
#include<queue>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef pair<int,int> pii;

const int MX = 1<<10;
int N, K, ans = 0;
pii D[MX*2];

struct Tree{
	int t[MX*2];
	void update(int x, int v){
		x += MX; t[x] = v;
		while(x > 1){
			x /= 2;
			t[x] = max(t[x*2], t[x*2+1]);
		}
	}
	int read(int s, int e){
		s += MX, e += MX;
		int mx = -1e9;
		while(s <= e){
			if(s&1) mx = max(mx, t[s++]);
			if(~e&1) mx = max(mx, t[e--]);
			s /= 2, e /= 2;
		}
		return mx;
	}
} A;

int deb = 1;
void solve()
{
	vector<int> C[MX];
	int U[MX] = {}, tmp[MX] = {};

	for(int i = 1; i <= K; i++) C[D[i].first].push_back(D[i].second);
	for(int i = 1; i <= N; i++) sort(C[i].begin(), C[i].end());
	for(int i = N; i >= 1; i--){	
		for(int j = 1; j <= N; j++) tmp[j] = 0;
		for(int c : C[i]) tmp[c] = 1;
		int cur = 0;
		for(int j = 1; j <= N; j++){
			if(tmp[j]) cur = 0;
			else cur += 1;
			
			if(cur == 0) U[j] = -1e9;
			else if(cur == 1) U[j] = U[j];
			else U[j] = max(U[j], cur);
		}
		for(int j = 1; j <= N; j++) U[j]++;
		for(int j = 1; j <= N; j++) A.update(j, U[j] + j); // to N

		set<int> B;
		for(int j = 1; j <= N; j++) B.insert(j);
		for(int j = i-1; j >= 1; j--){
			for(int c : C[j]){
				B.erase(c);
				A.update(c, -1e9);
			}
			vector<pii> interval;
			int st = 1;
			for(int c : C[j]){
				if(st != c) interval.emplace_back(st, c-1);
				st = c+1;
			}
			if(st != N+1) interval.emplace_back(st, N);
			
			if(j == i-1) continue; // at least one move required
			for(pii c : interval){
				int s, e; tie(s, e) = c;
				auto it = B.lower_bound(s);
				if(it == B.end() || *it >= e) continue;
				int v = A.read(*it+1, e) - *it + (i-j)*2 - 2;
				ans = max(ans, v);
			}
		}
	}
}

void rot90(){ for(int i = 1; i <= K; i++) D[i] = pii(D[i].second, N+1-D[i].first); }
void flip(){ for(int i = 1; i <= K; i++) D[i].second = N+1 - D[i].second; }

int main()
{
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= K; i++){
		scanf("%d%d", &D[i].first, &D[i].second);
	}
	for(int i = 1; i <= 8; i++){
		solve();
		if(i%4) rot90();
		else flip();
	}
	printf("%d\n", ans);
}

Compilation message

planet.cpp: In function 'int main()':
planet.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
planet.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &D[i].first, &D[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grader.c: In function 'void count_increment(const char*)':
grader.c:74:103: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'int' [-Wformat=]
   printf("Incorrect\ncount_%s()를 %d회보다 많이 호출했습니다.\n", limit_count_calls,  func);
                                                                                                       ^
grader.c:74:103: warning: format '%d' expects argument of type 'int', but argument 3 has type 'const char*' [-Wformat=]
grader.c: In function 'int main()':
grader.c:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &seed, &range);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccHAypSk.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/ccgeZY0X.o:planet.cpp:(.text.startup+0x0): first defined here
/tmp/ccHAypSk.o: In function `main':
grader.c:(.text.startup+0x1a1): undefined reference to `ainta()'
grader.c:(.text.startup+0x1b0): undefined reference to `sangsoo()'
collect2: error: ld returned 1 exit status