Submission #150222

#	Time	Username	Problem	Language	Result	Execution time	Memory
150222		서울대학교 연구공원 944동 삼성전자서울대연구소 (#200)	On the Grid (FXCUP4_grid)	C++17	43 / 100	14 ms	384 KiB

grid

#include "grid.h"

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int ans[3050];
bool chk[3050];
vector<int> SortDisks(int N) {
	if (N > 250) {
		vector <int> Vl;
		return Vl;
	}

	for (int q = 1; q <= N; q++) {
		vector <int> Vb;
		for (int i = 0; i < N; i++) if (chk[i]) Vb.push_back(i);
		sort(all(Vb), [](int a, int b) {
			return ans[a] > ans[b];
		});
		for (int i = 0; i < N; i++) if (!chk[i]) Vb.push_back(i);
		reverse(all(Vb));

		int v = PutDisks(Vb);
		if (v == N) {
			for (int i = 0; i < N; i++) ans[Vb[i]] = i + 1;

			vector <int> Va;
			for (int i = 0; i < N; i++) Va.push_back(ans[i]);
			return Va;
		}

		int st = 0, en = N - q, mi;
		while (st < en) {
			mi = (st + en) / 2;
			
			vector <int> Vq;
			for (int i = 0; i < N; i++) {
				if (i < st || i > en) Vq.push_back(Vb[i]);
				else if (i < st + en - mi) Vq.push_back(Vb[i + mi + 1 - st]);
				else Vq.push_back(Vb[i - en + mi]);
			}

			int v2 = PutDisks(Vq);
			if (v2 == N) {
				for (int i = 0; i < N; i++) ans[Vq[i]] = i + 1;

				vector <int> Va;
				for (int i = 0; i < N; i++) Va.push_back(ans[i]);
				return Va;
			}

			if (v2 == v + mi + 1 - st) {
				st = mi + 1;
			}
			else en = mi;
		}
		ans[Vb[st]] = v + st + 1 - N;
		chk[Vb[st]] = true;
	}

	vector <int> Va;
	for (int i = 0; i < N; i++) Va.push_back(ans[i]);
	return Va;
}

Compilation message (stderr)

grid.cpp:25:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 
grid.cpp:26:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")

• Subtask 1: 12 / 12
• Subtask 2: 31 / 31
• Subtask 3: 0 / 57