QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#914916#1990. RestaurantsAA_Surely#AC ✓193ms68864kbC++232.6kb2025-02-25 19:40:262025-02-25 19:40:36

Judging History

This is the latest submission verdict.

  • [2025-02-25 19:40:36]
  • Judged
  • Verdict: AC
  • Time: 193ms
  • Memory: 68864kb
  • [2025-02-25 19:40:26]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

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

#define fr first
#define sc second

#define vc vector
#define pb push_back

#define all(x) x.begin() , x.end()

#define Heh ios::sync_with_stdio(false) , cin.tie(0)

/*
const int MAXN = 1e3 + 13;
const ld err = 1e-12;

int par[MAXN] , rnk[MAXN];

int get(int v){return par[v] = (par[v] == v ? v : get(par[v]));}
void uni(int a , int b){
  a = get(a) , b = get(b);
  if(a == b) return;
  if(rnk[a] < rnk[b]) swap(a , b);
  par[b] = a;
  rnk[a] += rnk[b];
}

ld dis(ld a , ld b , ld c , ld d){
  return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}
*/

ll pw(ll a , ll b , ll mod){
  ll ret = 1;
  while(b){
    if(b&1) ret = (ret * a) % mod;
    a = (a * a) % mod;
    b /= 2;
  }
  return ret;
}

/*
const int MAXN = 3e5 + 35 , p = 313 , mod = 1e9 + 7;

string s;
int n , hsh[MAXN] , pp[MAXN] , inv[MAXN];

int hshsub(int l , int r){
  int ret = hsh[r];
  if(l){
    ret -= hsh[l-1];
    if(ret < 0) ret += mod;
  }
  ret = (1ll * ret * inv[l]) % mod;
  return ret;
}
*/

int main(){
  Heh;
  int n , m;
  cin >> n >> m;
  int c[m];
  for(int i = 0 ; i < m ; i++) cin >> c[i];
  vc<int> pn[n];
  cin.ignore();
  for(int i = 0 ; i < n ; i++){
    string s;
    getline(cin , s);
    s += ' ';
    string t;
    for(char c : s){
      if(c == ' '){
	if(t == "") continue;
	pn[i].pb(stoi(t) - 1);
	t = "";
      }
      else t += c;
    }
  }
  vc<int> pm[m];
  map<int,int> mpn[m];
  for(int i = 0 ; i < m ; i++){
    string s;
    getline(cin , s);
    s += ' ';
    string t;
    for(char c : s){
      if(c == ' '){
	if(t == "") continue;
	pm[i].pb(stoi(t) - 1);
	t = "";
      }
      else t += c;
    }
    for(int j = 0 ; j < (int)pm[i].size() ; j++){
      mpn[i][pm[i][j]] = j;
    }
  }
  int pt[n] = {};
  set<int> atr[m];
  queue<int> nos;
  for(int i = 0 ; i < n ; i++) nos.push(i);
  while(nos.size()){
    int i = nos.front();
    nos.pop();
    while(pt[i] < pn[i].size()){
      int j = pn[i][pt[i]];
      if((int)atr[j].size() < c[j]){
	atr[j].insert(mpn[j][i]);
	break;
      }
      else if(*prev(atr[j].end()) > mpn[j][i]){
	int k = pm[j][*prev(atr[j].end())];
	atr[j].erase(prev(atr[j].end()));
	nos.push(k);
	atr[j].insert(mpn[j][i]);
	break;
      }
      pt[i]++;
    }
  }
  vc<int> ans;
  for(int i = 0 ; i < m ; i++){
    while(atr[i].size()){
      ans.pb(pm[i][*atr[i].begin()]);
      atr[i].erase(atr[i].begin());
    }
  }
  sort(all(ans));
  for(int x : ans) cout << x+1 << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

input:

5 2
2
1
1
2
1
2
1
5 3 1
2 4

output:

2
3
5

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

5 2
2
3
1
2
1
2
1
5 3 1
2 4

output:

2
3
4
5

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

5 6
1
5
5
5
5
5
1
1
1
1
1
3 1 5 4 2
0
0
0
0
0

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

3 3
1
1
1
1
2
2 3
1
3 2
3

output:

1
3

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

3 3
1
1
1
1
2 3
2 3
1
2 3
3 2

output:

1
2
3

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 107ms
memory: 59008kb

input:

1000 1000
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
50...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 4ms
memory: 4864kb

input:

10000 1
5000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

5001
5002
5003
5004
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
...

result:

ok 5000 lines

Test #8:

score: 0
Accepted
time: 62ms
memory: 17848kb

input:

50000 4
5000
5000
5000
5000
2 1 3 4
3 2 4 1
4 3 2 1
2 4 3 1
1 3 2 4
3 1 4 2
3 4 2 1
2 1 3 4
2 3 4 1
2 1 4 3
2 4 3 1
2 4 1 3
1 2 4 3
1 2 4 3
4 1 3 2
2 4 1 3
1 4 3 2
1 4 2 3
3 4 1 2
4 3 1 2
1 4 3 2
3 4 1 2
4 2 1 3
2 4 1 3
2 3 1 4
3 1 2 4
1 2 4 3
4 2 3 1
1 2 3 4
1 2 4 3
1 2 3 4
4 3 1 2
4 1 3 2
3 1 4 2
...

output:

30001
30002
30003
30004
30005
30006
30007
30008
30009
30010
30011
30012
30013
30014
30015
30016
30017
30018
30019
30020
30021
30022
30023
30024
30025
30026
30027
30028
30029
30030
30031
30032
30033
30034
30035
30036
30037
30038
30039
30040
30041
30042
30043
30044
30045
30046
30047
30048
30049
30050
...

result:

ok 20000 lines

Test #9:

score: 0
Accepted
time: 5ms
memory: 7424kb

input:

10000 10000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 10000 lines

Test #10:

score: 0
Accepted
time: 63ms
memory: 22272kb

input:

10000 100
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50...

output:

1
2
4
5
9
17
18
20
24
25
27
28
31
32
33
34
35
36
37
38
40
44
45
46
47
49
51
53
55
56
59
61
63
64
65
66
67
69
71
73
76
81
83
86
87
88
90
92
93
94
96
99
101
105
107
108
112
114
115
116
118
121
126
127
130
131
133
135
136
137
141
144
145
146
150
156
157
159
160
161
163
164
165
169
172
179
181
184
185
1...

result:

ok 5000 lines

Test #11:

score: 0
Accepted
time: 155ms
memory: 67668kb

input:

50000 10000
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 50000 lines

Test #12:

score: 0
Accepted
time: 193ms
memory: 68864kb

input:

50000 10000
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 50000 lines

Test #13:

score: 0
Accepted
time: 178ms
memory: 64384kb

input:

50000 10000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 10000 lines