CSES - Putka Open 2015 – finaali

Submission details
Task:	Ravintola
Sender:
Submission time:	2015-12-20 13:35:25 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	15
#2	ACCEPTED	41
#3	ACCEPTED	44

Test results
test	verdict	time	group
#1	ACCEPTED	0.06 s	1	details
#2	ACCEPTED	0.06 s	1	details
#3	ACCEPTED	0.06 s	1	details
#4	ACCEPTED	0.05 s	1	details
#5	ACCEPTED	0.05 s	1	details
#6	ACCEPTED	0.06 s	2	details
#7	ACCEPTED	0.06 s	2	details
#8	ACCEPTED	0.07 s	2	details
#9	ACCEPTED	0.07 s	2	details
#10	ACCEPTED	0.06 s	2	details
#11	ACCEPTED	0.29 s	3	details
#12	ACCEPTED	0.29 s	3	details
#13	ACCEPTED	0.30 s	3	details
#14	ACCEPTED	0.30 s	3	details
#15	ACCEPTED	0.30 s	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < crd.size(); ++i) {
                      ^
input/code.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < pois[i].size(); ++j) {
                          ^
input/code.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < lisaa[i].size(); ++j) {
                          ^

Code

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int MN = 5e5+100;
int t[MN][2];
int ans[MN];
vector<int> lisaa[MN];
vector<int> pois[MN];
int main() {
    int n;
    cin>>n;
    vector<int> crd;
    for(int i = 0; i < n; ++i) {
        cin>>t[i][0]>>t[i][1];
        crd.push_back(t[i][0]);
        crd.push_back(t[i][1]);
    }
    sort(crd.begin(), crd.end());
    crd.erase(unique(crd.begin(), crd.end()), crd.end());
    unordered_map<int, int> mp;
    for(int i = 0; i < crd.size(); ++i) {
        mp[crd[i]] = i;
    }
    for(int i = 0; i < n; ++i) {
        lisaa[mp[t[i][0]]].push_back(i);
        pois[mp[t[i][1]]].push_back(i);
    }

    int m = 0;
    vector<int> tyhjat;
    for(int i = 0; i < MN; ++i) {
        for(int j = 0; j < pois[i].size(); ++j) {
            tyhjat.push_back(ans[pois[i][j]]);
        }
        for(int j = 0; j < lisaa[i].size(); ++j) {
            if(tyhjat.size()) {
                ans[lisaa[i][j]] = tyhjat.back();
                tyhjat.pop_back();
            }
            else {
                ans[lisaa[i][j]] = m;
                ++m;
            }
        }
    }
    cout<<m<<'\n';
    for(int i = 0; i < n; ++i) {
        cout<<ans[i]+1<<'\n';
    }

}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`10 78 83 61 70 95 100 84 100 ...` view save

correct output
`6 5 5 2 1 ...` view save

user output
`6 5 5 2 1 ...` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`10 90 98 99 100 96 100 3 47 ...` view save

correct output
`4 1 1 3 1 ...` view save

user output
`4 1 4 3 1 ...` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`10 65 87 89 97 32 53 53 73 ...` view save

correct output
`5 5 4 3 3 ...` view save

user output
`5 5 5 3 3 ...` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`10 54 68 50 60 87 89 85 98 ...` view save

correct output
`6 6 3 4 1 ...` view save

user output
`6 6 3 5 1 ...` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`10 53 54 41 47 56 68 6 23 ...` view save

correct output
`5 2 2 2 2 ...` view save

user output
`5 2 2 2 2 ...` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`1000 421639537 911563318 736166797 959945771 397431507 584367626 330835287 620406496 ...` view save

correct output
`358 264 215 218 262 ...` view save

user output
`358 264 317 218 262 ...` view save

Test 7

Group: 2

Verdict: ACCEPTED

input
`1000 452773897 489658400 791565174 873685909 837939163 961670907 54444659 861374731 ...` view save

correct output
`393 181 151 140 63 ...` view save

user output
`393 181 151 340 63 ...` view save

Test 8

Group: 2

Verdict: ACCEPTED

input
`1000 689073468 881081127 613328959 683799585 688380485 930935455 629559449 915788743 ...` view save

correct output
`388 115 358 93 170 ...` view save

user output
`388 210 358 349 46 ...` view save

Test 9

Group: 2

Verdict: ACCEPTED

input
`1000 376658209 496021591 750793088 930681206 293307485 666877615 774206996 816529147 ...` view save

correct output
`368 287 36 225 114 ...` view save

user output
`368 287 82 225 131 ...` view save

Test 10

Group: 2

Verdict: ACCEPTED

input
`1000 273998160 725204323 241875005 614630291 765984835 939309031 345615468 836277449 ...` view save

correct output
`384 240 215 156 163 ...` view save

user output
`384 240 215 238 243 ...` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`100000 784035755 893627685 78761690 459329957 877042231 976087228 479438596 515807337 ...` view save

correct output
`36779 4699 7608 7073 23546 ...` view save

user output
`36779 4699 7608 29256 26031 ...` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`100000 952007928 998571741 60494193 790262572 37935588 450716710 518464251 658961939 ...` view save

correct output
`36979 5145 5964 3813 17811 ...` view save

user output
`36979 28532 5964 3813 14563 ...` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`100000 195552215 647391707 698053972 908728728 923590842 940850158 17166936 129136741 ...` view save

correct output
`36760 17563 24436 3901 1722 ...` view save

user output
`36760 17563 5860 34070 1722 ...` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 792681664 892304133 442916094 984949977 880260482 922213143 417012279 978533731 ...` view save

correct output
`36633 5062 11088 8773 23538 ...` view save

user output
`36633 30613 11088 21991 8908 ...` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`100000 662244341 835857878 88360474 126816291 245452241 989480216 32665049 226410123 ...` view save

correct output
`36920 28994 8379 21303 3304 ...` view save

user output
`36920 35172 8379 21303 3304 ...` view save

Putka Open 2015 – finaali

Ravintola

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions ()