p171.cpp
======================
#include <bits/stdc++.h>
using namespace std;

struct Zone {
    int q, cap, id;
};

struct Student {
    int p, w, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K;
    cin >> K;

    vector<Zone> zones(K);
    long long totalN = 0;
    for(int i = 0; i < K; i++) {
        cin >> zones[i].cap;
        totalN += zones[i].cap;
    }

    for(int i = 0; i < K; i++) {
        cin >> zones[i].q;
        zones[i].id = i;
    }

    vector<Student> students(totalN);
    for(int i = 0; i < totalN; i++) {
        cin >> students[i].p;
    }

    for(int i = 0; i < totalN; i++) {
        cin >> students[i].w;
        students[i].id = i;
    }

    sort(students.begin(), students.end(), [&](auto& a, auto& b) {
        return a.w > b.w;
    });

    sort(zones.begin(), zones.end(), [&](auto& a, auto& b) {
        return a.q < b.q;
    });

    vector<int> answer(totalN, -1);

    for(auto& st: students) {
        int bestZoneIndex = -1;
        for(int j = K - 1; j >= 0; j--) {
            if(zones[j].q < st.p && zones[j].cap > 0) {
                bestZoneIndex = j;
                break;
            }
        }
        if(bestZoneIndex != -1) {
            answer[st.id] = zones[bestZoneIndex].id + 1;
            zones[bestZoneIndex].cap--;
        }
    }

    int zIndex = 0;
    for(int i = 0; i < totalN; i++) {
        if(answer[i] == -1) {
            while(zIndex < K && zones[zIndex].cap == 0) {
                zIndex++;
            }
            answer[i] = zones[zIndex].id + 1;
            zones[zIndex].cap--;
        }
    }

    for(int i = 0; i < totalN; i++) {
        cout << answer[i] << (i + 1 < totalN ? ' ' : '\n');
    }

    return 0;
}

=================
statement.txt
======================
171. Sarov zones
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



It is known that to participate the All-Russian Mathematic Olympiad one should do one of other olympiads enough good. These olympiads are called "zone olympiads" and the region from which people participate the same zone olympiad is called "zone". Sarov city of Nizhny Novgorod district is situated near the boundary of zones, so every year school students of Sarov participate several zones.

This year K zones invited students from Sarov to participate their olympiads. i-th zone invited N[i] students, so N=N[1]+N[2]+...+N[K] totally students were invited. After the Sarov city olympiad, N students were selected, so now the olympiad authorities of Sarov have to decide, which students will participate which zone olympiad. Each student is characterized by his olympiad level and each zone is characterized by its zone level. If a student with olympiad level P participates zone with zone level Q, he will be invited to All-Russian olympiad if and only if P>Q.

Every student is also characterized by his "weight". The Sarov olympiad authorities want, that the All-Russian Olympiad will be participated by students with maximal summary weight. You are to help them. Write a program which will divide the students between zones. Keep in mind that exactly N[i] students can go to i-th zone.

Input
On the first line of input there is an only integer K (1<=K<=100). On the second line there are K integers N[1], N[2], ... ,N[K] (0<=N[i]<=16000). On the third line there are K more integers Q[1], Q[2], ... ,Q[K] --- the zone levels of the zones. On the fourth line there are N integers P[1], P[2], ... P[N] --- olympiad levels of the students. (0<=Q[i]<=1000000, 0<=P[i]<=1000000). On the last (and fifth) line there are N integers w[1], w[2], ... w[k] --- the "weights" of students. 0<=w[i]<=100000. It is also guaranteed that 0<=N<=16000.

Output
Output only N integers --- Z[1], Z[2], ... Z[N] --- the numbers of zones which should be participated by students 1, 2, ... N.

Sample test(s)

Input
2
1 1
4 1
2 3
2 1

Output
2 1
Author:	NNSU #2 team
Resource:	
Date:	






=================
