p171.ans1
======================
2 1

=================
p171.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

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

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

int k;
int64_t total_n;
vector<Zone> zones;
vector<Student> students;

void read() {
    cin >> k;
    zones.resize(k);
    total_n = 0;
    for(int i = 0; i < k; i++) {
        cin >> zones[i].cap;
        total_n += zones[i].cap;
    }

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

    students.resize(total_n);
    for(int i = 0; i < total_n; i++) {
        cin >> students[i].p;
    }

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

void solve() {
    // A student qualifies for the All-Russian olympiad iff his level p exceeds
    // his zone's level q. To maximise total qualifying weight we greedily
    // process students by decreasing weight; sort zones by increasing level
    // and place each student into the highest-level zone that still has free
    // capacity and that he can beat (q < p). This keeps low-level zones free
    // for weaker students who can only qualify there. Any students left
    // unassigned are poured into whatever capacity remains, in zone order.

    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(total_n, -1);

    for(auto& st: students) {
        int best_zone = -1;
        for(int j = k - 1; j >= 0; j--) {
            if(zones[j].q < st.p && zones[j].cap > 0) {
                best_zone = j;
                break;
            }
        }

        if(best_zone != -1) {
            answer[st.id] = zones[best_zone].id + 1;
            zones[best_zone].cap--;
        }
    }

    int zi = 0;
    for(int i = 0; i < total_n; i++) {
        if(answer[i] == -1) {
            while(zi < k && zones[zi].cap == 0) {
                zi++;
            }

            answer[i] = zones[zi].id + 1;
            zones[zi].cap--;
        }
    }

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

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p171.in1
======================
2
1 1
4 1
2 3
2 1

=================
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:	






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