oj.uz

답안 #516443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516443 2022-01-21T10:19:57 Z shivensinha4 Take-out (POI13_usu) C++17
22 / 100
 42 ms 65540 KB 
#include "bits/stdc++.h"
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k; cin >> n >> k;
	string s; cin >> s;
	
	vi pref(n);
	vector<deque<int>> prefpos(3*n);
	for_(i, 0, n) {
		if (s[i] == 'c') pref[i] = -k;
		else pref[i] = 1;
		
		if (i) pref[i] += pref[i-1];
		
		prefpos[pref[i]+n].push_back(i);
	}
	
	function<void(int, int)> solve = [&] (int l, int r) {
		if (l > r) return;
		
//		cout << "solving " << l << " " << r << endl;
		int prepref = (l > 0 ? pref[l-1] : 0);
		
//		cout << "\tgot previous prefix: " << prepref << endl;
		assert(pref[r] == prepref);
		
		while (prefpos[prepref+n].size() and prefpos[prepref+n].front() < l) prefpos[prepref+n].pop_front();
//		cout << "\ttaking from " << prefpos[prepref+n].size() << endl;
		int firstpos = prefpos[prepref+n].front();
		
		/*if (l == 1 and r == 6) {
//			cout << "\tprefix sum: " << prepref << " is remaining at positions: " << prefpos[prepref+n] << endl;
//			return;
		}*/
		
		assert(firstpos <= r);
		if (firstpos != r) {
//			cout << "\tyep splitting " << firstpos << endl;
			solve(l, firstpos);
			solve(firstpos+1, r);
			return;
		}
		
		prefpos[prepref+n].pop_front();
		
		for_(opt, 0, k+2) {
			int va = (l+opt-1 >= 0 ? pref[l+opt-1] : 0) - (l > 0 ? pref[l-1] : 0);
			int sufopt = k+1-opt;
			int vb = pref[r] - (r-sufopt >= 0 ? pref[r-sufopt] : 0);
			
			if (va+vb == 0) {
				vi ans;
				for_(i, l, l+opt) ans.push_back(i);
				for_(i, r-sufopt+1, r+1) ans.push_back(i);
				
				for (auto i: ans) cout << i+1 << " ";
				cout << endl;
				
//				cout << "should have gone to " << l+opt << " " << r-sufopt << " from " << l << " " << r << endl;
				solve(l+opt, r-sufopt);
				return;
			}
		}
		
//		cout << "uhhh found nothing " << l << " " << r << endl;
//		assert(false);
	};
	
	solve(0, n-1);
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 844 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 2 ms 3532 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16588 KB Output is correct
2 Correct 11 ms 20412 KB Output is correct

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 42 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 38 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -