제출 #1342173

#제출 시각아이디문제언어결과실행 시간메모리
1342173top1svtinJJOOII 2 (JOI20_ho_t2)C++17
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

#define kien long long
#define int long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<int, int>
#define dembit(a) __builtin_popcountll(a)
#define task "kien"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define debug(x) cout << x << " "
#define down cout << "\n"
const kien MOD = 1e18 + 7;
const int NTEST = 100;
const int Million = 1e6;
const int MXN = 2e5 + 5;
const int INF = 1e9;

mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
	assert(l <= r);
	return uniform_int_distribution<kien>(l, r)(rd);
}

kien n, k, m, u, v, h, xuong[MXN], pre[MXN], len[MXN];
kien maxx, minn, sum, vtr, s, t, r, x, l, timer, ans, add;
vector <int> dau, cuoi, mid;

int tknp (int kk) {
	int l = 0, r = dau.size() - 1;
	int kq = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (dau[mid] <= kk) l = mid + 1, kq = mid;
		else r = mid - 1;
	}
	return kq;
}

int tknp1 (int kk) {
	int l = 0, r = cuoi.size() - 1;
	int kq = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (cuoi[mid] >= kk) l = mid + 1, kq = mid;
		else r = mid - 1;
	}

	return kq;
}

void solve() {
	cin >> n >> k;
	string s; cin >> s;
	FOR (i, 0, s.size() - 1) {
		if (i > 0)
		pre[i] = pre[i - 1];
		if (s[i] == 'J') dau.pb(i);
		if (s[i] == 'O') ++pre[i], mid.pb(i);
	}

	FORD (i, s.size() - 1, 0) {
//		suf[i] = suf[i + 1];
		if (s[i] == 'I') cuoi.pb(i);
	}

	if (dau.size() < k or cuoi.size() < k or mid.size() < k) {
		cout << "-1\n"; return;
	}

	int dem = 0;
	FOR (i, 0, dau.size() - 1) {
		if (i < k) {if (i > 0) len[i] = len[i - 1] + (dau[i] - dau[i - 1] - 1);}
		else len[i] = (len[i - 1] - len[i - k]) + (dau[i] - dau[i - 1] - 1);
	}

	FOR (i, 0, cuoi.size() - 1) {
		if (i < k) {if (i > 0) xuong[i] = xuong[i - 1] + (cuoi[i - 1] - cuoi[i] - 1);}
		else xuong[i] = (xuong[i - 1] - xuong[i - k]) + (cuoi[i - 1] - cuoi[i] - 1);
	}

	FOR (i, 0, k - 2) len[i] = xuong[i] = -1;

	int dd = 0, cc; ans = INF;
	FOR (i, k - 1, mid.size() - 1) {
		cc = i;
		int tren = tknp1(mid[cc]); int duoi = tknp(mid[dd]);
		if (tren == -1 or duoi == -1) continue;
//		cout << dau[duoi] << " " << cuoi[tren] << "\n";
		++dd;
		if (len[duoi] == -1 or xuong[tren] == -1 or pre[cuoi[tren]] - pre[dau[duoi] - 1] < k) continue;
		ans = min(ans, len[duoi] + xuong[tren] + (cuoi[tren] - dau[duoi] - 1 - k));
	}

	if (ans == INF) {cout << -1; return;}
	cout << ans << "\n";
}

main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if (fopen(task".inp", "r")) {
		fin(task); fou(task);
	}

	int tt = 1; // cin >> tt;
	while(tt--) {
		solve();
	}

	cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t2.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main() {
      | ^~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
ho_t2.cpp:108:17: note: in expansion of macro 'fin'
  108 |                 fin(task); fou(task);
      |                 ^~~
ho_t2.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:108:28: note: in expansion of macro 'fou'
  108 |                 fin(task); fou(task);
      |                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...