oj.uz

Submission #255158

# Submission time Handle Problem Language Result Execution time Memory
255158 2020-07-31T12:43:02 Z shayan_p popa (BOI18_popa) C++14
100 / 100
 109 ms 500 KB 
// And you curse yourself for things you never done

#include "popa.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1010, mod = 1e9 + 7, inf = 1e9 + 10;

int aft[maxn], bef[maxn];
/*
int S[maxn];

bool query(int l1, int r1, int l2, int r2){
    int g1 = 0, g2 = 0;
    while(l1 <= r1)
	g1 = __gcd(g1, S[l1]), l1++;
    while(l2 <= r2)
	g2 = __gcd(g2, S[l2]), l2++;
    return g1 == g2;
}
*/

int solve(int n, int *L, int *R){
    stack<int> st;
    for(int i = 0; i < n; i++){
	while(sz(st) && query(st.top(), i, i, i) )
	    aft[ st.top() ] = i, st.pop();
	bef[i] = (st.empty() ? -1 : st.top());
	st.push(i);
    }
    while(sz(st)){
	aft[st.top()] = n;
	st.pop();
    }   
    for(int i = 0; i < n; i++){
	L[i] = R[i] = -1;
    }
    int ans = -1;
    for(int i = 0; i < n; i++){
	if(bef[i] == -1 && aft[i] == n){
	    ans = i;
	    continue;
	}
	if(bef[i] == -1){
	    L[ aft[i] ] = i;
	    continue;
	}
	if(aft[i] == n){
	    R[ bef[i] ] = i;
	    continue;
	}
	if(bef[ aft[i] ] == bef[i]){
	    L[ aft[i] ] = i;
	}
	else{
	    R[ bef[i]]  = i;
	}
    }
    return ans;
}
/*
int L[maxn], R[maxn];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> S[i];
    }
    cout << "HEY " << solve(n, L, R) << endl;
    for(int i = 0; i < n; i++){
	cout << L[i] << " " << R[i] << endl;
    }
    return 0;
}
*/

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 256 KB Output is correct
2 Correct 10 ms 256 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 500 KB Output is correct
2 Correct 93 ms 388 KB Output is correct
3 Correct 71 ms 384 KB Output is correct
4 Correct 88 ms 384 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 376 KB Output is correct
2 Correct 109 ms 388 KB Output is correct
3 Correct 104 ms 492 KB Output is correct
4 Correct 95 ms 376 KB Output is correct