oj.uz

Submission #958000

# Submission time Handle Problem Language Result Execution time Memory
958000 2024-04-04T15:49:37 Z vjudge1 Lottery (CEOI18_lot) C++17
45 / 100
 2804 ms 1136 KB 
//* Nigga we hit em up like mutherfucking Tupac Shakur

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
      
using namespace std;
using namespace __gnu_pbds;
      
template <typename T>
using oset = tree<T,null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update>;
      
#define int long long
          
#define pb push_back
#define ins insert
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
  
          
using ll = long long;
using ld = long double;

#define endl '\n'

#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
        
#define da cout<<"DA"<<endl
#define ne cout<<"NE"<<endl
          
#define send ios::sync_with_stdio(false);
#define help cin.tie(0);
          
void solve(int T);
          
const int N = 2005;
const int M = 5e5 + 10;
const int SQRT = sqrt(N);
const int LOG = 20;
const int INF = 1e18;
const int MOD = 123456789;
const ld EPS = 1e-9;

  
//int ans;
int n, m,k, q, l, r, x, y, z, mx, mn;
  
  
          
int32_t main(){
    auto begin = chrono::high_resolution_clock::now();
    cout<<setprecision(7)<<fixed;
              
    send help;
          
    int tt = 1;
    //cin>>tt; //? Comment if no testcases
    for(int i = 1;i<=tt;i++){
        cerr<<"Case "<<i<<": "<<endl;
        solve(i);
    }
    auto end = chrono::high_resolution_clock::now();
    cerr<<"Time: "<<chrono::duration_cast<chrono::duration<double>>(end - begin).count()<<endl;
    return 0;
}

int A[N];

int ans[105][N];

void solve(int T){
    int l; 
    cin>>n>>l;

    for(int i = 0;i<n;i++)cin>>A[i];
    cin>>q;
    pair<int,int> que[q];
    for(int i = 0;i<q;i++){
        int x;
        cin>>x;
        que[i] = {x, i};
    }

    sort(que, que + q);

    //int ans[q][n];

    for(int i = 0;i+l-1<n;i++){
        deque<int> x, y;
		for (int j = i;j<i+l;j++)x.push_back(A[j]);
		for (int j = 0;j<l;j++)y.push_back(A[j]);
		int cnt = 0;
		for (int k = 0;k<l;k++) {
			if (x[k] != y[k]) cnt++;
		}
		vector<int> v;
		if (i) v.push_back(cnt);
		for (int j = l;j <n;j++) {
			y.pop_front();
			y.push_back(A[j]);
			if (j - l + 1 == i) continue;
			cnt = 0;
			for (int k = 0;k<l;k++) {
				if (x[k] != y[k]) cnt++;
			}
			v.push_back(cnt);
		}
		sort(all(v));
		int p = 0;

		for(int k = 0;k<q;k++){
			while (p < v.size() && v[p] <= que[k].first) p++;
			ans[que[k].second][i] = p;
		}
    }

    for(int i = 0;i<q;i++){
        for(int j = 0;j+l-1 < n;j++)cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}   
  
  
  
//! Te molam da raboti !!

Compilation message

lot.cpp: In function 'void solve(long long int)':
lot.cpp:116:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    while (p < v.size() && v[p] <= que[k].first) p++;
      |           ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 9 ms 600 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 7 ms 564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 9 ms 600 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 7 ms 564 KB Output is correct
13 Correct 103 ms 576 KB Output is correct
14 Correct 2793 ms 988 KB Output is correct
15 Correct 2804 ms 820 KB Output is correct
16 Correct 1669 ms 1076 KB Output is correct
17 Correct 2154 ms 908 KB Output is correct
18 Correct 2175 ms 1136 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 9 ms 600 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 7 ms 564 KB Output is correct
13 Correct 103 ms 576 KB Output is correct
14 Correct 2793 ms 988 KB Output is correct
15 Correct 2804 ms 820 KB Output is correct
16 Correct 1669 ms 1076 KB Output is correct
17 Correct 2154 ms 908 KB Output is correct
18 Correct 2175 ms 1136 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -