oj.uz

답안 #918776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918776 2024-01-30T12:29:42 Z waldi Monochrome Points (JOI20_monochrome) C++17
35 / 100
 2000 ms 10440 KB 
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

struct przedzialowiec{
	int N;
	vector<int> t;
	przedzialowiec(int n){
		for(N = 1; N <= n;) N <<= 1;
		t.resize(N<<1, 0);
	}
	void dodaj(int poz){
		for(poz+=N; poz; poz>>=1) ++t[poz];
	}
	int suma(int p, int k){
		int ret = 0;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret += t[p++];
			if(k&1) ret += t[--k];
		}
		return ret;
	}
};

int main(){
	int n;
	scanf("%d\n", &n);
	int n2 = n<<1;
	vector<int> s(n2);
	REP(i, n2){
		char c;
		scanf("%c", &c);
		s[i] = c=='B';
	}
	
	int wyn = 0;
	REP(xd, n){
		vector<pii> prz;
		
		vector<vector<int>> lewo(2), prawo(2);
		REP(i, n) lewo[s[i]].emplace_back(i);
		FOR(i, n, n2-1) prawo[s[i]].emplace_back(i);
		REP(i, ssize(lewo[0])) prz.emplace_back(lewo[0][i], prawo[1][i]);
		REP(i, ssize(lewo[1])) prz.emplace_back(lewo[1][i], prawo[0][i]);
		
		int tmp = 0;
		sort(all(prz));
		przedzialowiec przed(n);
		REP(i, n){
			pii t = prz[i];
			tmp += przed.suma(0, t.se-n);
			przed.dodaj(t.se-n);
		}
		wyn = max(wyn, tmp);
		
		s.insert(s.begin(), s.back());
		s.pop_back();
	}
	printf("%d", wyn);
	return 0;
}

Compilation message

monochrome.cpp: In function 'int main()':
monochrome.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d\n", &n);
      |  ~~~~~^~~~~~~~~~~~
monochrome.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%c", &c);
      |   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 7 ms 452 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 4 ms 344 KB Output is correct
21 Correct 4 ms 348 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 4 ms 348 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 4 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 3 ms 344 KB Output is correct
30 Correct 3 ms 344 KB Output is correct
31 Correct 4 ms 344 KB Output is correct
32 Correct 4 ms 344 KB Output is correct
33 Correct 4 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 7 ms 452 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 4 ms 344 KB Output is correct
21 Correct 4 ms 348 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 4 ms 348 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 4 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 3 ms 344 KB Output is correct
30 Correct 3 ms 344 KB Output is correct
31 Correct 4 ms 344 KB Output is correct
32 Correct 4 ms 344 KB Output is correct
33 Correct 4 ms 348 KB Output is correct
34 Correct 357 ms 596 KB Output is correct
35 Correct 354 ms 532 KB Output is correct
36 Correct 347 ms 344 KB Output is correct
37 Correct 315 ms 592 KB Output is correct
38 Correct 262 ms 516 KB Output is correct
39 Correct 286 ms 512 KB Output is correct
40 Correct 257 ms 344 KB Output is correct
41 Correct 230 ms 516 KB Output is correct
42 Correct 349 ms 516 KB Output is correct
43 Correct 302 ms 344 KB Output is correct
44 Correct 313 ms 512 KB Output is correct
45 Correct 298 ms 344 KB Output is correct
46 Correct 324 ms 536 KB Output is correct
47 Correct 294 ms 536 KB Output is correct
48 Correct 305 ms 344 KB Output is correct
49 Correct 258 ms 344 KB Output is correct
50 Correct 276 ms 512 KB Output is correct
51 Correct 305 ms 344 KB Output is correct
52 Correct 362 ms 596 KB Output is correct

Subtask #4
0.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 7 ms 452 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 4 ms 344 KB Output is correct
21 Correct 4 ms 348 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 4 ms 348 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 4 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 3 ms 344 KB Output is correct
30 Correct 3 ms 344 KB Output is correct
31 Correct 4 ms 344 KB Output is correct
32 Correct 4 ms 344 KB Output is correct
33 Correct 4 ms 348 KB Output is correct
34 Correct 357 ms 596 KB Output is correct
35 Correct 354 ms 532 KB Output is correct
36 Correct 347 ms 344 KB Output is correct
37 Correct 315 ms 592 KB Output is correct
38 Correct 262 ms 516 KB Output is correct
39 Correct 286 ms 512 KB Output is correct
40 Correct 257 ms 344 KB Output is correct
41 Correct 230 ms 516 KB Output is correct
42 Correct 349 ms 516 KB Output is correct
43 Correct 302 ms 344 KB Output is correct
44 Correct 313 ms 512 KB Output is correct
45 Correct 298 ms 344 KB Output is correct
46 Correct 324 ms 536 KB Output is correct
47 Correct 294 ms 536 KB Output is correct
48 Correct 305 ms 344 KB Output is correct
49 Correct 258 ms 344 KB Output is correct
50 Correct 276 ms 512 KB Output is correct
51 Correct 305 ms 344 KB Output is correct
52 Correct 362 ms 596 KB Output is correct
53 Execution timed out 2029 ms 10440 KB Time limit exceeded
54 Halted 0 ms 0 KB -