oj.uz

Submission #307779

# Submission time Handle Problem Language Result Execution time Memory
307779 2020-09-29T09:57:32 Z b00n0rp Finding Routers (IOI20_routers) C++17
100 / 100
 7 ms 496 KB 
#include "routers.h"
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i = 0; i < n; i ++)
#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 vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define remin(a,b) a = min(a,b)
#define remax(a,b) a = max(a,b)
 
vi find_routers(int l, int n, int q) {
    vi ans;
    vector<pii> quer;
    ans.pb(0);
    FOR(i,1,n){
    	int low = ans.back()+1,high = l-2*(n-1-i)+1,mid;
    	for(auto x:quer){
    		if(x.S < i-1) continue;
    		else if(x.S == i-1) remax(low,x.F+1);
    		else if(x.S >= i){
    			remin(high,x.F-2*(x.S-i));
    		}
    	}
    	while(low < high){
    		mid = (low+high)/2;
    		if(ans.back()+2*(mid-ans.back()-1)+2*(n-i-1) > l){
    			high = mid-1;
    			continue;
    		}
    		int c = use_detector(mid);
    		quer.pb({mid,c});
    		if(c < i){
    			low = mid+1;
    		}
    		else if(c == i){
    			high = mid;
    		}
    		else{
    			high = mid-1;
    		}
    	}
    	ans.pb(ans.back()+2*(low-ans.back()-1));
    }
    return ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 5 ms 496 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 7 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 6 ms 416 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct