Task: | Ruudukko |
Sender: | EeliH |
Submission time: | 2022-11-06 22:05:49 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | ACCEPTED | 33 |
#3 | ACCEPTED | 39 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 2, 3 | details |
#7 | ACCEPTED | 0.61 s | 3 | details |
#8 | ACCEPTED | 0.70 s | 3 | details |
#9 | ACCEPTED | 0.99 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:142:18: warning: unused variable 't' [-Wunused-variable] 142 | __int128 t = (rr + rr1 + 1) % AAAA; | ^
Code
#include <bits/stdc++.h>using namespace std;const __int128 AAAA = 1000000007;__int128 reitit[1000][1000];__int128 ruudukko[1000][1000];pair<int, pair<int, int>> rows[1000][1000];pair<int, pair<int, int>> cols[1000][1000];__int128 reititcols[1000][1000];__int128 reititrows[1000][1000];int colsij[1000][1000];int rowsij[1000][1000];__int128 aacols[1000];__int128 aarows[1000];__int128 oacols[1000];__int128 oarows[1000];int ec[1000];int er[1000];__int128 maaralaske_reitit = 0;__int128 maaralaske_reitit_nopea = 0;bool rowcolcmp(pair<int, pair<int, int>> i, pair<int, pair<int, int>> j){return i.first < j.first;}int main(){int n;priority_queue<pair<int, pair<int, int>>> q;cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int arvo;//cin >> ruudukko[i][j];cin >> arvo;ruudukko[j][i] = arvo;q.push(make_pair(-arvo, make_pair(j, i)));rows[i][j] = make_pair(arvo, make_pair(j, i)); // :/cols[j][i] = make_pair(arvo, make_pair(j, i)); // ** :/ **reitit[i][j] = -1;}aacols[i] = 0;aarows[i] = 0;oacols[i] = 0;oarows[i] = 0;ec[i] = 0x7fffffff;er[i] = 0x7fffffff;}for (int i = 0; i < n; i++) {sort(rows[i], rows[i]+n, rowcolcmp);sort(cols[i], cols[i]+n, rowcolcmp);for (int j = 0; j < n; j++) {pair<int, int> a = cols[i][j].second;pair<int, int> b = rows[i][j].second;colsij[a.first][a.second] = j;rowsij[b.first][b.second] = j;}}/*for (int j = 0; j < n; j++) {for (int i = 0; i < n; i++) {//cout << rows[i][j].first << endl;cout << i << ", " << j << ": " << colsij[i][j] << endl;}}*///cout << "BEGIN --------------\n";__int128 nreitit = 0;while (!q.empty()) {pair<int, pair<int, int>> a = q.top();int i = a.second.first;int j = a.second.second;int b = -a.first;q.pop();//cout << "------------- " << i << ", " << j << ": " << b << endl;if (ec[i] != b) {aacols[i] += oacols[i];oacols[i] = 0;}if (er[j] != b) {aarows[j] += oarows[j];oarows[j] = 0;}int acol = colsij[i][j] - 1;int edellinen = -1;__int128 rr = 0;__int128 rc = aacols[i];for (int k = acol; k >= 0; k--) {pair<int, pair<int, int>> d = cols[i][k];int c = d.first;if (c == b) {continue;}if (edellinen != -1 && c < edellinen) {break;}edellinen = c;rr = (rr + reitit[d.second.first][d.second.second]) % AAAA;}int arow = rowsij[i][j] - 1;edellinen = -1;__int128 rr1 = 0;__int128 rw = aarows[j];for (int k = arow; k >= 0; k--) {pair<int, pair<int, int>> d = rows[j][k];int c = d.first;if (c == b) {continue;}if (edellinen != -1 && c < edellinen) {break;}edellinen = c;rr1 = (rr1 + reitit[d.second.first][d.second.second]) % AAAA;//cout << "- " << d.second.first << ", " << d.second.second << endl;//cout << k << " " << rr1 << " " << rw << endl;}//cout << "rrrr: " << (long long) rr << " " << (long long) rc << " " << (long long) rr1 << " " << (long long) rw << endl;//__int128 t = (rr + rr1 + rw + rc) % AAAA;__int128 t = (rr + rr1 + 1) % AAAA;//cout << "--" << endl;//cout << (int64_t) t << endl;//cout << (int64_t) (t + rw + rc) << endl;oacols[i] = (oacols[i] + rw + rc + 1) % AAAA;oarows[j] = (oarows[j] + rw + rc + 1) % AAAA;er[j] = b;ec[i] = b;//reititrows[j][i] = t;//reititcols[i][j] = t;//reititrows[j][i] = rr1;//reititcols[i][j] = rr;//reititrows[j][i] = (rr1 + rw) % AAAA;//reititcols[i][j] = (rr + rc) % AAAA;reitit[i][j] = (rw + rc + 1) % AAAA;nreitit += (rw + rc + 1) % AAAA;}nreitit %= AAAA;cout << (int64_t) nreitit << endl;//cout << "Määrä laske_reitit: " << maaralaske_reitit << endl;//cout << "Määrä laske_reitit nopea: " << maaralaske_reitit_nopea << endl;}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 1 1 1 1 1 1 1 1 1 |
correct output |
---|
9 |
user output |
---|
9 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 1 2 3 6 5 4 7 8 9 |
correct output |
---|
135 |
user output |
---|
135 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 7 8 1 4 5 4 3 9 6 |
correct output |
---|
57 |
user output |
---|
57 |
Test 4
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
10000 |
user output |
---|
10000 |
Test 5
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
187458477 |
user output |
---|
187458477 |
Test 6
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 2995 8734 1018 2513 7971 5063 ... |
correct output |
---|
964692694 |
user output |
---|
964692694 |
Test 7
Group: 3
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1000000 |
user output |
---|
1000000 |
Test 8
Group: 3
Verdict: ACCEPTED
input |
---|
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
229147081 |
user output |
---|
229147081 |
Test 9
Group: 3
Verdict: ACCEPTED
input |
---|
1000 520283 805991 492643 75254 527... |
correct output |
---|
951147313 |
user output |
---|
951147313 |