oj.uz

Submission #523170

# Submission time Handle Problem Language Result Execution time Memory
523170 2022-02-07T07:12:29 Z mansur Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 6500 KB 
#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
 
//01001101 01100001 01101011 01101000 01100001  01100111 01100001 01111001 
 
using namespace std;
 
#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()                                                                   
#define ld double
#define ull unsigned long long
#define ff first                                         
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>                          
#define E exit (0)
#define int long long
 
const int inf = 1e15, N = 5e3 + 1, mod = 998244353;                    
 
double eps = 1e-6;
 
vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
main() {                                                         
	//freopen("F.in", "r", stdin);                                                                                     
	//freopen("F.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(NULL);                                                                                       
	cin.tie(NULL);
	int k, n;
	cin >> k >> n;
	char t1[n + 1], t2[n + 1];
	int p1[n + 1], p2[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> t1[i] >> p1[i] >> t2[i] >> p2[i];
	}
	if (k == 1) {
		vector<int> s;
		for (int i = 1; i <= n; i++) {
			if (t1[i] != t2[i]) { 	
				s.pb(p1[i]);
				s.pb(p2[i]);
			}
		}
		sort(all(s));
		int p = -1;
		if (sz(s)) p = s[sz(s) / 2];
		int ans = inf;
		for (int i = -100; i <= 100; i++) {
			p += i;
			int cur = 0;
			for (int j = 1; j <= n; j++) {
	    		if (t1[j] == t2[j]) {
	    			cur += abs(p2[j] - p1[j]);
	    			continue;
	    		}
	    		cur += abs(p1[j] - p) + abs(p2[j] - p) + 1;	
	    	}
	    	p -= i;
	    	ans = min(ans, cur);
	    }
	    cout << ans;
	}else {
		int ans = inf;
	    for (int i = 1; i <= n; i++) {
	    	int pl = p1[i];
	    	for (int j = 1; j <= n; j++) {
	    		int pr = p1[j], cur = 0;
	    		for (int s = 1; s <= n; s++) {
	    			if (t1[s] == t2[s]) {
	    				cur += abs(p2[s] - p1[s]);
	    				continue;
	    			}
	    			cur += min(abs(p1[s] - pl) + abs(p2[s] - pl), abs(p1[s] - pr) + abs(p2[s] - pr)) + 1;;	
	    		}
	    		ans = min(ans, cur);
	    		pr = p2[j], cur = 0;
	    		for (int s = 1; s <= n; s++) {
	    			if (t1[s] == t2[s]) {
	    				cur += abs(p2[s] - p1[s]);
	    				continue;
	    			}
	    			cur += min(abs(p1[s] - pl) + abs(p2[s] - pl), abs(p1[s] - pr) + abs(p2[s] - pr)) + 1;;	
	    		}
	    		ans = min(ans, cur);
	    	}
	    	pl = p2[i];
	    	for (int j = 1; j <= n; j++) {
	    		int pr = p1[j], cur = 0;
	    		for (int s = 1; s <= n; s++) {
	    			if (t1[s] == t2[s]) {
	    				cur += abs(p2[s] - p1[s]);
	    				continue;
	    			}
	    			cur += min(abs(p1[s] - pl) + abs(p2[s] - pl), abs(p1[s] - pr) + abs(p2[s] - pr)) + 1;;	
	    		}
	    		ans = min(ans, cur);
	    		pr = p2[j], cur = 0;
	    		for (int s = 1; s <= n; s++) {
	    			if (t1[s] == t2[s]) {
	    				cur += abs(p2[s] - p1[s]);
	    				continue;
	    			}
	    			cur += min(abs(p1[s] - pl) + abs(p2[s] - pl), abs(p1[s] - pr) + abs(p2[s] - pr)) + 1;;	
	    		}
	    		ans = min(ans, cur);
	    	}
	    }
	    cout << ans;	
	}
}

Compilation message

bridge.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      | 
bridge.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 58 ms 4972 KB Output is correct
13 Correct 69 ms 6456 KB Output is correct
14 Correct 55 ms 5168 KB Output is correct
15 Correct 43 ms 3868 KB Output is correct
16 Correct 65 ms 5948 KB Output is correct
17 Correct 59 ms 6452 KB Output is correct
18 Correct 83 ms 6168 KB Output is correct
19 Correct 67 ms 6500 KB Output is correct
20 Correct 57 ms 6080 KB Output is correct
21 Correct 65 ms 6244 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 10 ms 308 KB Output is correct
4 Correct 13 ms 308 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 12 ms 308 KB Output is correct
8 Correct 12 ms 204 KB Output is correct
9 Correct 12 ms 308 KB Output is correct
10 Correct 15 ms 204 KB Output is correct
11 Correct 13 ms 304 KB Output is correct
12 Correct 12 ms 204 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 10 ms 204 KB Output is correct
4 Correct 10 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 12 ms 204 KB Output is correct
8 Correct 12 ms 312 KB Output is correct
9 Correct 12 ms 304 KB Output is correct
10 Correct 13 ms 204 KB Output is correct
11 Correct 13 ms 304 KB Output is correct
12 Correct 13 ms 308 KB Output is correct
13 Execution timed out 2067 ms 204 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 13 ms 204 KB Output is correct
4 Correct 12 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 11 ms 312 KB Output is correct
8 Correct 13 ms 308 KB Output is correct
9 Correct 12 ms 308 KB Output is correct
10 Correct 14 ms 204 KB Output is correct
11 Correct 16 ms 204 KB Output is correct
12 Correct 14 ms 312 KB Output is correct
13 Execution timed out 2075 ms 204 KB Time limit exceeded
14 Halted 0 ms 0 KB -