結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー bal4u
提出日時 2019-07-09 08:43:00
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,648 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 250 ms
コンパイル使用メモリ 30,848 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 06:18:49
合計ジャッジ時間 1,493 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff #
raw source code 

// yukicoder: No.684 Prefix Parenthesis
// 2019.7.9 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	do *s = gc();
	while (*s++ > ' ');
	*(s-1) = 0;
}

typedef struct { int l, r, d; } T;
T t[100005], s[100005]; int tz, sz;
char S[100005]; int N;
long long ans;

int cmpt(const void *a, const void *b) {
	return ((T *)a)->r - ((T *)b)->r;
}

int cmps(const void *a, const void *b) {
	int t = ((T *)b)->d - ((T *)a)->d;
	if (t) return t;
	return ((T *)b)->l - ((T *)a)->l;
}

int main()
{
	int i, l, r;
	long long ls, rs;

	N = in(), ins(S);
	l = r = ls = rs = 0;
	for (i = 0; i < N; i++) {
		if (S[i] == '(') l++;
		else {
			if (l) l--, ans += N-i;
			else r++;
		}
		if (r == 0) ls += l;
		else if (l == 0) rs += r;
		else if (l-r >= 0) t[tz].l = l, t[tz++].r = r;
		else s[sz].l = l, s[sz].r = r, s[sz++].d = l-r;
	}
//	printf("sz=%d, ans=%lld, ls=%d, rs=%d\n", sz, ans << 1, ls, rs);
//	for (i = 0; i < sz; i++) printf("%d(, %d)\n", t[i].l, t[i].r);
	
	qsort(t, tz, sizeof(T), cmpt);
	for (i = 0; i < tz; i++) {
		if (t[i].r <= ls) ans += t[i].r, ls -= t[i].r;
		else ans += ls, ls = 0;
		ls += t[i].l;
	}
	qsort(s, sz, sizeof(T), cmps);
	for (i = 0; i < sz; i++) {
		if (s[i].r <= ls) ans += s[i].r, ls -= s[i].r, s[i].r = 0;
		else ans += ls, s[i].r -= ls, ls = 0;
		ls += s[i].l;
	}
	ans += (ls <= rs)? ls: rs;
	printf("%lld\n", ans << 1);
	return 0;
}
0